Minor Factions and unique features
A lot of random map generators make a strange and kind of bland world. I was thinking that it could incorporate some unique features with quests and inhabitants. Say a mist shrouded island full of corsairs or a mountain valley with rich resources and some caverns containing a goblin horde. The minor factions could be mostly restricted to a small area and either protect unique technologies or other rewards. Conquering the corsairs could both remove them as a threat and provide you with technology to improve your navy. A forest full of friendly beings could provide a unique bonus in return for protection. Protect the hobbits and they trade a happiness increasing beer to all your cities. Maybe a deadly desert that will kill your units unless you trade with the desert nomads for the tech to allow safe passage. Each set piece would be designed by developers or fans and you could let it be dropped into an otherwise randomly generated map. A fantasy world should have unique features rather than a civilization style map.