Many years ago I was chosen as one of the Alpha testers for Elemental:War_of_Magic. I was eager to provide my software consulting experience and my decades love of fantasy games to assist with creating what was planned to be the spiritual sequel for Master of Magic! I won't share those old stories, but after six years I will share advice of what I've seen allow other fantasy games become legendary... such as Heroes 3 and Age of Wonders:Shadow Magic.
1) Random Map Generator - Allowing randomly generated maps greatly increases replay value. I recognize Stardock is already doing this with many games, but it's worth mentioning. Games missing the random map generation will be forgotten more quickly since repetition becomes boring.
2) Map Editor - Allowing the gaming community to create custom maps for their fellow gamers provides a win for the gamers who are seeking new challenges, a win for the gamers who enjoy creating and giving their work to others and a win for Stardock because it keeps the gaming community alive longer. Some of my best fun has been knowing I've provided a popular map for the community.
3) Multiplayer - After 6 years I was shocked to see still no multiplayer for the fantasy games. Sure single player can be fun, but unless you hate your relatives and loved ones the single player massively pales in comparison to having an entire family play together as a team and/or as competition. The multiplayer is what's allowed games such as Heroes 3 and Age of Wonders: Shadow Magic to keep evolving! Heroes 3 has Wake of God and Age of Wonders: Shadow Magic released the 1.5 unofficial patch about 6 months ago. These games contain multiplayer and thrived.
4) Game Modding - Allowing the community to modify and evolve parts of the game has been extremely successful for many games. One of the best examples is probably the Civilization series... hopefully we see more modding options in future Stardock games. On a side note the games with the most active modding communities are multiplayer games.
Hope this helps.