Well, like I said, I've only given this cursory thought, but I imagine the outline would be something like the following:
Divide the map of ardania into provinces. Each noble house the player can choose from has an associated starting province.
Each province has an associated quest. One you complete that quest, you gain control of that province, and can move on to quests in adjacent provinces.
At the same time, other noble houses are competing to complete quests in their neighbouring provinces. Later on, you can try to wrest control of provinces from rival houses through conquest or succession. (And naturally, the converse can occur.)
Controlling a province gives you added resources for either embellishing your capital, or founding new colonies in outlying territories. (A little like Zeus, as you suggested.) Completing a quest usually twinks you out with special artifacts, and of course a portion of your cash and heroes can be carried from quest to quest.
Kidnappings, sabotage, subversion or rebellion, religious conversions and diplomatic missions, or supernatural events like Vendral awakening or Url Shekk being summoned could also be triggered to spice things up. Certain boss-monsters and their followers could effectively behave like rival houses, while requiring hunts for special artifacts to permanently defeat.
So basically, you'd have a little bit of pre-scripted story in the form of individual provinces' quest material, but the overall narrative is something that emerges from the order in which you tackle quests, the large-scale ethical and tactical decisions you make, and how your allies and rivals in turn react to that.
In other words, very similar to a 'Lite' version of what you'd see in crusader kings, which is kind of why I hoped Paradox would jump all over this.