Oi, 4,000,000 hexes. What a huge game it would be; probably it would take months to reach a decisive point.
1UPT would not be so bad here as well. The time scale may also need reducing, maybe by a factor of 10?
I would absolutely love to play this new game that has:
-4,000,000 hexes
-1UPT
-Strong Multiplayer capacities (possibly 48-144 players)
-Such dynamic and different resources like the ones in Civ4
-Competent AI (this would take a while to develop, I would prefer huge multiplayer games)
-Great/Less expensive buildings like the ones in Civ4
-More specific units for specific eras
-The ability to conglomerate a formation of units into a front, which can be controlled/moved/rotated in any direction with just a few clicks (NOT 1000s of clicks)
-Time at 4000 BC starting at rates of 4 years - in the Modern Era, turns pass by weekly
-It doesn't need the great graphics; nice 128 x 128 2D sprites and health bars and such are fine with me (anti-aliasing doesn't matter that much either to me)
-Ranged units, that actually seem more realistic.
-Multi-level mountains, for example hills, high hills, crossable mountains, and impassable mountains
-A nice built in voice chat system such as ventrilo or skype (this would keep everyone on for hours)
-More permanent diplomatic events (no more 10-turn peace treaties, each negotiation counts for quite a while)
-A 1-3 turn period of time to make decisions before actually voting on a resolution/gifting a tech/accepting a peace treaty
-Game speed could be increased by dividing the map into several 1000 areas around 1000-2000 tiles in size; this could render the area YOU are looking at much faster, and it would not impose nearly as much processing power on the other 1000s of areas (kind of like how a computer doesn't use RAM to store a 10 GB program, for example)
I am kinda sorry I just rambled on a bit, these ideas just kept popping in my head and I felt like posting them. The point is that I would love 20km hexes.