I don't see how a story (good/bad) is going to have any impact on game play. I would like to see more character interaction and/or random events with npc's. Where not every npc can be hired, trusted, married. Interacting with npc's would be far more interesting than managing buildings in a city. Some npc's would bring you quests or want something in return for joining you.

Npc (I am my own man/women)

- each ncp would have their own likes/dislikes hidden (your empire/magic type/npc/npc type/your people/war/peace/other kingdoms/attracted/not-attracted/etc.).

- The more time you spend with an npc (fighting/adventure/quests completed)  the more you would learn about your npc's, their likes/dislikes are revealed.

Npc actions (some npc's just can't be trusted)

- Treason/seduction/cheating/stealing(tech, spells, equipment)/assignation/npc runs off with your prince/princess/spouse/revolt/have a child with unwed princess/kidnap members of your royal family

- Image your spouse decides he/she likes an npc more then you and they take over a city and become a neutral kingdom while your out adventuring.

Npc  (let's make a deal)

- Some npc's can to get you into trouble, I will help you today if your just do me one little favor.

- Give/trade resources/gold/map/tech/spell/equipment/etc. for a princess or if you kill another npc.

- What will you be willing to give an npc for a scroll with a secret spell or location of a treasure or location.

- Npc tries to sell you the location of where an sovereign is going to be or could be just a trap.

Loyalty

- where each npc has a loyalty rating to you and your empire, that can change depending on your actions and their likes/dislikes.

- Buying them new equipment will improve loyalty.

- Trusting them to send on adventures/quests would improve loyalty.

- Allow them to marry into to your royal family.

- Spending more time with your spouse/hiers.

- Install an npc with power/rank as the governor of a city

- Endow an ncp with a title (Duke/Duchess/Sir/lord/lady/etc.)

- Promote an npc as the head of your army or captan of the city guards, etc.

As far as role playing games go there is nothing better than having a NPC/enemy hero that you actually get angry at.

I posted something somewhat similar in that each of the npc's should have descriptors that dictate personality. Much like Talents in the sovereign creation screen. Brilliant, Cruel, and Mischievous, the Magus Molsk has preferences towards what type of leader or culture he'd be interested in serving based on the descriptors for that leader or culture. If you're really smart and can teach some badass spells then Molsk will respect you but if you are Kind he might see that as weakness. This could influence the cost of the NPC and the morale of the NPC.