More.. and this time some more fantastic/inventive ideas..
Terrain improvements like farmlands and roads/railroads can be built only to certain % of land around city.. and that % depends of city size. That way it will be more realistic - not all the terrain ain't filled with terrain improvements, but some forests remain even in late game.
Special terrain buildings. Some way to implement bridges, tunnels passing mountains and canals.
Elevated terrain like in Alpha Centaury, and not terrain restrictions to units, but terrain features that restrict certain units.. do you guys understand, it's turned around,.. not under units are the restrictions, but under terrains there should be restrictions for mounted, wheeled, "big body", foot, not amphibious etc. Also like in Alpha Centauri, sea level might change, even SHOULD change slowly over long time period.. that is until global warming makes it drastically change.
Villages as first size of the settlement, and most of these doesn't grow beyound that - villages have less building oportunities, but in times when cities grow big, nearby villages supply some really needed food.
Big number of smaller nations.. well i'm one of these who would really like at least 50 civs,.. and that managing large empire would be much more trickier than small country. Still, downside of small country would be danger in war situations or when dealing with disasters or barbarians.
Appocalypse.. chance that end of the world comes, when you don't deal with early signs of global warmth or other global problems.
Alliances that doesn't require your participation in wars, yet this gives your ally to broke alliance. Without a cause it is permanent. Other causes may be not accepting with deals and treaties or when you don't give aid when ally is struck by disaster.
Diplomatic Aid.. when civ gets enough diplomatic aid from peaceful civs, warmonger AI may more probably start peace negotiations with them and player agressor gets more respect from these peaceful civs, when you start negotiations.
Big agressive empires have more stress in relations with each other, than small countries.
Subterran and underwater option for building.. in case there will be some future eras included.
Robotic units, again for future eras - they are more or less automatic, and may sometimes have errors and therefore do unexpected things, like turning against your friendlies or against yourself, yet robots are not affected by chemical warfare, they traverse some terrain that is unpassable for humans, they never need population to be built, and reduce war weariness.
Idea that nukes destroy city is good, but then maybe there should be nuclear fallout shelters, so that even when your city is destroyed, your people comes out of the shelter as a settler and worker.. to start from the beginning again.
Option to change civ to play in midgame, if you have that option checked before starting the game. In that way, if you get so powerful that game doesn't seem fun anymore, you can try to fight against that civ you just built up.
Techtree, or actually part of it depends of the environment and resources you control and of diplomatical/political decisions you have made. So, when you mostly have dry land, for your civ is important to learn better ways to obtain and transport water,.. or when your civ has been agressive lately, it gets more militaristic technologies.
Civ4 great leader/great person system sounds nice.
Strategic markers for showing allies where to concentrate their attack
AI should use terrain strategically - is it asked too much
Piracy and terrorism as espionage options + offcourse negotiations to stop such actions.
Civil Wars.. these offcourse shouldn't occure randomly, splitting great countries into two,.. but happen when some causes are met, like serious unhappiness + low culture/economy/long lasting war weariness; different culture groups in one country (uses first idea from my post above or because the captured people of different culture) etc. New country should perhaps be named after largest city. Small unrests should put revolutionary units around a revolting town, like in Civ2.
More interesting small scenarios.. well, this is optional, as if we can have a decent editor, community probably produces tons of these.
Some cities may merge in modern times and/or in future, becoming metropolises, that have especially high economy, cultural growth and industrial power, and also gives tactical defencive ground around it. But such metropolises can also be conquered, taking only one part of it - This may result two enemies having cities alongside each other, without any empty square between.