1) I'd like the attire of the leaders to change over time, as in Civ III.
2) Make espionage less overwhelming. Make spies more expensive to produce and reintroduce a maximum number of 5. Also, it should be possible to discover which other nation is behind the theft of a technology or a terrorist outrage. Not a certainty that one finds out, but the possibility to do so should be there. For the technology theft, one could legitimately ask for monetary or other compensation, and if the compensation isn't forthcoming go to war without suffering any damage to one's reputation, though one must first ask for compensation to escape the damage. (The compensation should be something the offending civ is able to hand over.) For terrorist attacks (poisoned water, blown up buildings and the like) one could choose to go to war without suffering any damage to one's reputation. If one chooses not to act on such an act of espionage or sabotage, that should make the perpetrating civ better disposoed towards you, unless they are furious and don't care. At the same time, successful missions should make a spy better at his/her job and able to do it at a cheaper price in espionage points.
3) I'd really like to see an end to the idiotic "50 turns left to victory!" and "25 turns left until the end of the game!" messages splashed on the screen. Players should be able to keep track of those things on their own. Also, if one chooses to play on after victory, the fact that the victory announcement remains on the screen is rather annoying too.
4) Include a diplomatic option to offer to pay for getting a city belonging to an opponent - in money or technology or a number of military units. If a city is of minor value to the opponent or isolated from their main terriory and at an inconvenient distance from it, or under peril to fall to a third civilization, the owner of the city might be willing to part for it, the price depending on how valuable or worthless the city is to him.
5) There is some music from Civ II and Civ III that I'd like to see return. In Civ II, there was a wonderful melody called "The World of Jules Verne" which appeared with industrialism. It reflected the optimism of 19th century industrial society. In Civ III, there was another melody which always played when you made the breakthrough to the industrial age - very cheerful and energetic. Both tunes could be used from industrialism onwards to indicate that your civ is flourishing. There was also a melody in the original Civ (the Aztec national theme) which doubled as the tune that told you a city had been captured by barbarians. I'd like to see it reintroduced for that purpose.
6) Bring back the High Council and the Throne Room from Civ II.
7) Introduce an option to turn cavalry units into tanks instead of helicopters. In most other countries than America, cavalry regiments became tank regiments, not airborne units. If tanks and choppers are deemed to be of different value, then let that be reflected by a difference in the upgrading price.
8) Give spies the ability to bribe barbarian units into joining your side. Also, include the ability to ask to buy units from other civs. One could perhaps even be able to buy units which reflect a technological level one has not yet attained, though that would not mean that one acquires the ability to reorduce them. After all, throughout history nations have hired or been lent units of foreign soldiers with technologies and expertise not available among their own people.
9) On a related note, introduce Swiss mercenaries one can hire - available from the Middle Ages to Indiustrialism! Expensive - you have to pay a somewhat hefty maintenance for them every turn, or they leave - but formidable soldiers. Footsoldiers - melee troops at first, then musketmen. Only a limited number on the market, and those you don't hire will probably be hired by others.
10) In Civ II, if you didn't like a suggested city name and dismissed it, it didn't turn up again during that game. It would be nice to see that one restoredn. Some people, for example, like to call Rome Roma, but if they do, they hahve to spend the rest fo the game renaming each successive city because "Rome" turns up every time you found a new one.
11) Let the barbarians be able to form minor civs after a certain stage in the game (the rise of Nationalism of one regular civ?) A maximum of, say, 3 cities. They can be dominated, bullied, bribed but not absorbed. Wooing them and making them your friends instead of your whipping boys might give you special advantages.
12) Finally, let the Great Artist "Frank Kafka" at last have his proper name of Franz Kafka restored to him. Never, at any time or by any people, was he called Frank. And why are terrorists such as Guy Fawkes and Anthony Babington included as Great Spies? Why not Richard Sorge and Leopold Trepper, who were two of the most skilled and successful spies during WWII? Walter Krivitsky, a Soviet agent who defected to the west in the 1930's, was a very skilled spy too. And then there were the two Hebrews who spied out the Promised Land - Joshua and Caleb.