Would love Volkswander: The Great Invasions. A game where you play a tribe in the chaos surrounding the fall of the Roman Empire. Sure, you control territory, but you're not leading a state, you're leading a people (represented by pops). You could conquer vast lands, but you only have a certain number of pops to populate that land with, and your conquered peoples are still there. If you spread yourself too thin you could end up like the huns and disappear. Of course, if you don't expand at all you'll also vanish into the dustbin of history. Over time, you could assimilate related peoples into your own kingship, and a thriving tribal people will of course grow to include new pops. Diplomatically a smaller tribe can also create or join a tribal confederacy, where several weaker tribes come together to increase their influence, at the cost of internal cohesion and the possibility of collapse if things don't go well. Defend against the Huns, exploit the collapse of the Roman Empire, and quiver against the unstoppable might of the Muslim conquests.
You'd have a very different experience ruling over Rome or Byzantium, as you'd have a greater focus on exploitation of land than management of your pops. They'd be much richer than tribes but pack less military ability per pop. These empires can settle allied tribes within their lands to improve the military fortunes of the empire, but if you don't keep them happy you might be inviting in your own doom.
I imagine you'd play from about 400 AD up until the (edit) death of Charlemagne in 812. I'm imagining a rather fluid pop-based game where control of land isn't as important as who the people occupying it are. The tribes I'm talking about are not even a little bit related to the way they're portrayed in CK2.