I would like every playthrough to be distinct, but I also want some sort of inertia and stability.
This is supposed to be a place where the main NPCs are descended from dynasties of traditions going back multiple generation. It is a bit weird that this immediately turns to a speedrun game of Risk.
But I don't want this to be forced. I want there to be flavour. If the queen of southern empire loses her main cities, I want her to have a special preference for getting them back. They mean something to her.
I want a Battanian lord to plunder the Aserai, but have a less desire of conquering and running desert cities because he simply is not keen on desert culture.
Of course, when a kingdom gets more different lords, then they also have lords that would like different things so you would have lords both liking to be lord at the icy mountains as well as the scolding hot desert , but at the expense of internal cohesion because these lords may not like eachother as much as those of similar culture.
I would like to see a lord having a special connection to a town (because of his backstory). And if I could offer him this city, then that would be very valuable to him. I would even like to offer him the city in advance (you will get it in 40 days) so that I could scheme against a kingdom and find discontent lords.
Likewise, that a lord of desert culture ruling a mountain city would be with some penalty.
And the effect of this would be that the starting kingdoms would have preference for a gradual expansion and have a tendency for behaving as cultural pillars rather than excel driven NPC economist.
I want every playthrough to be unique, but I want cultural flavor and the feeling of a world where the background story makes sense. It doesn't make sense that Aserai have been at the same place for 700 years, but then they swap place with the battanians within 2 years with the kingdom just being "business as usual".
This mechanic could also create stable/unstable regions. Particuarily, the empire would have a number of holdings who other houses in other factions felt they had a du jure claim for. Whereas nobody thought they had a du jure claim for Aserai territory.