1. Use the hex-grid to make a spherical, 3d world map. I want to be able to fly planes across the arctic circle!
2. Evolving civilization traits. I would like to see the decisions I make during the game slowly mold the culture of my civilization.
3. Revolutions/Minor Civs/Civil War. The late game in vanilla civ 4 gets very static, and happiness and unhealthiness were merely mild inconveniences rather than a real threat to my winning the game.
4. Multi-turn combats between units. In Civ 4 there were all these cool experience upgrades, but one bad battle and you lost everything. It would be nice of units wouldn't always die after one round of combat.
5. Advisor videos. The old videos from Civ 2 were highly entertaining, if cheesy. Bringing these back would add some flavor to the game.
6. Changing leader attire/background over time. In Civ 3, the leaders' apperance would change during different eras. In Civ 4, the music changed, but the background was always the same, which was jarring. It would be nice if their attire changed with the music.
7. Better music for the modern age. Minimalism is a relatively small musical movement from the 20th century. Some neo-classical or, heck, even some Jazz, would be nice, and much less distracting. The music in the modern era tended to make me zone out and lose focus.
8. Unique unit skins for each unit for each civ. This is the upgrade I most liked from the Legends of Revolutions mod. Having unique skins on a civ-by-civ basis made the civs feel more different, even though practically the units behaved the same.
9. More interesting economic and resources system. It would be nice to see an ability to turn resources into finished goods like in Colonization and then trade them. not as micro-level as Colonization, but it'd be cool to specialize economic production in cities beyond simply changing what abstract resources they provide (money, culture, science).
10. More detail in some time-periods that were glazed over. For example, the enlightenment era was sort of glazed over, when that was a major time of social upheaval. The enlightenment and industrial eras, at least in terms of combat, need to be fleshed out, especially since, from a military standpoint, the represented a major change in how combat was conducted.
11. Finally, bring back Leonardo's Workshop!