I'm planting this idea here, so as to not distract from the LH discussions as it doesn't involve that game.
I always thought spies in Galactic Civilizations were cool, and think a similar concept would be appropriate in E:WOM, especially with Dynasties in play.
Thinking about some uses for them, I came up with this rather unrelated idea...
What if there was an 'Auction house' function (similar to how the Galactic Council shows up in GC), where every so many turns a list of heroes was made available, and the various empires submitted bids for their services, opening up the whole bidding war mechanic? This could also work for rare relics. A player might not have need of a particular quest item, so they put it up for auction, and the other empires/kingdoms submit bids.
Fame points (borrowing from LH) could be used for bidding, along with gildar, perhaps with a stronger 'weighting' for Fame.
Heroes would still appear via the lore mechanic, of course, but said appearances would be adjusted to balance against this new source. Just a thought...
Another idea might be to have minor empires provide heroes for hire from time to time. So, essentially, you send a unit/diplomat to the local minor empire, and you discover a hero for hire. This could be part of the Shop, or appear in the dialog window for a given city. Also, I've always felt that minor empires could play stronger roles in the game (instead of just something to conquer). Perhaps they produce quest items or other items of importance that the player needs? Lore perhaps? Said abilities would be lost if conquered, increasing your motivation to NOT conquer them.
Minor empires could also be a source of marriage interests for your Sovereign and/or kids.
Back on the spy front, it might be fun to allow spies to bribe heroes to leave another sovereign's employ, and join your Sovereign... this could work for certain unit types too. I'd suggest that, if the spy is successful, that he is consumed in the process as a game balancing feature, with a limited number of spies being available/limited production of course. Spies could also act as assassins, taking out enemy heroes as well, with some percentage being assigned to success/failure. Sovs could be targetted as well (lower success rate), but of course would just be immobilized for a few turns instead of killed.
I've always liked the idea of sabotage too. Taking out someone's shard temple might be an interesting distraction...
Ahh, well. There's a start.