1) Speed up unit production.
2) Permit 2 units per hex (a mini stack). This shows a combined force, not just spearmen. It would still be weak vs the 3rd unit type, but, nowhere as extreme as the SOD.
3) Allow ships to fire far inland 2-3 hexes (I hear they might do one).
4) Go beyond Stealth to the next gen units, not crazy cyborgs or mechs, which will never happen. Such as longer range Fighter/Bombers or Battleships that can carry missles.
5) Improve the middle years, where early gunpowder units would use pistols, and add Gatling Guns for a US Civil War style game.
6) Have a larger selection of stone age units, not just a warrior, or a UU.
Start the game 1-6,000 years earlier, and slow tech so, you can actually fight multiple battles with multiple armys with the same tech level, not always having to chase the next upgrade.
7) Be able to set the time frame so, that the game progress only up to a certain age, say the middle ages, they no more teching. This was done sucessfully in the Empire Earth series.
8) Bring back Ships attacking land units. What a better way to make ships more useful?
9) Add another tile base, such as raised Hills. I live at sea level, and I get tht Mt. Everest, in game terms is not passable, but, there is many 1000s of feet of elevation between the two, taken up by one tile called, "hills".
10) Create more structures outside of a city that can be raided. Such as a river dam, 2nd and 3rd row of walls, even the ability to "steal" a resourse for 1 turn (say steel used for weapons) to upgrade a unit right there in the battlefield, because, he just took swords and a shield from your blacksmith. Something like a goody hut that grants a promotion, but, every city has it, because, they built a blacksmith in it.
11) Add FlameThrowers to take down structures or even forests.
12) Add Snipers, and Modern Snipers.
13) Advanced Attack Helocopters. 2010s Helos are much more effective than 1960s Helos.
14) Add Ballistas to early seige warfare (Greeks and Romans used them).
15) Add Sappers to take down walls (used everywhere by everyone around the world).
16) Have 2-3 UUs per Civ.
17) Add disease to weaken units, before hospitals or vaccines are researched, or before a medic is in the army.
18) Add weather, such as fog near warm zone lakes, random snow near northern lakes.
19) How about the occasional Barbarian Sea animal early? Your canoe got eaten by a shark, or galley damaged by a whale.
20) Bring back multiple leaders for each Civ. Or al least have the option to load a different name and face built into the game. If we want Richard the LionHeart during our Middle Age game, let us have that option.
Probably, more, but, I'll stop, and take a breath, lol, for now.