There's some great stuff in this thread.
As for dungeons, I believe a mixture of randomly generated and fixed encounters would be good.
You are out scouting and find a mountainside with many caves. As you explore these caves you will have a % chance to encounter one or more enemy groups. The reward will be scaled to the danger. Greater danger, greater reward. I think this is a pretty standard system that works well with keeping things different everytime.
I'm not sure how to weave story into these randomly generated dungeons, unless clearing the dungeon starts a pre-written quest arc that gets picked from a pool of story arcs.
People could write these arcs (in workshop?) and submit them to be rated and put in for others to download. Problem here is that you would need a lot of story arcs to make a pool large enough so that you'll have something new everytime. Also, I'm guessing these arcs will have map requirements of some kind. Beat any of these dungeons to start arc. Dungeon X will advance plot to chapter 2, dungeon Y to chapter 3 etc. But then the map would need to meet these requirements or generate dungeons mid game.
Perhaps there's a more elegant solution.
I think only really epic things should fall under the core Stardock storyline. There was mention of Imperium Galactica 2 earlier and I feel a similar way of handling story would be a very good way. Specific events popping up randomly as you play. So while you might know what to do after a runthrough, the challenges will be different due to other players/starting conditions/lay of the land or whatever.
It still keeps things interesting but allows Stardock to put in a tight, controlled storyline.
Other fixed storyline moments could be single, one off dungeon encounters. Though the degree at which we can interact with dungeons/landmarks will dictate how detailed a story we can engage with imo.
If dungeons are just things we go into to, fight a battle and click Take All, I think the reason why we went into it can be easily forgotten. HoMM did that a lot and I really didn't care after a while. What it lacked was the uniqueness. Oh it's just another tower battle map.... it's just another x/y/z. There's a lack of RPG style exploration, or at least an overview of where you are to give it a bit more meaning.
That's my food for thought. I'm quite behind on my elemental lurking so need to see what info has been released on dungeons etc.
EDIT: What about the ability to add your own names to some of the smaller/generic dungeons or landmarks? Whoever discovers it first will give it a name or if you can't be bothered, a randomly generated one. If there are intelligent creatures/primitive tribes living in them, have them already named unless you clear them out and claim the land.