In Civ 4, I have really really missed the throne room and city view. These ought to be brought back. Yeah, they are just graphics with no real effect on the game and therefore represent an unnecessary encumbrance on the engine, but the thing is, they don't have to be.
Amen to that. And I'd also like to see the High Council back, the way they were in Civ II, looking different and speaking differently depending on which historical stage you are at. ("All is well, sire. I'm off to oil my abacus!" "Would you let your soldiers sleep in latrines? Build barracks first, other improvements later!" "My talents go to waste, my lord! Let us contact other civilizations to exchange knowledge!" "I concur, your majesty." "Wise men say a good ruler gives his subjects some entertainment... king." "No! Hah! Build city walls!" All the way to: "Let's do lunch, sir.") Those were funny; similar utterances (I'd even like to see some of those I quoted return) could be great. (Back then, the High Council and the trips to the Throne Room could be turned off by those who didn't enjoy them, and of course that feature should be retained.)
However, during anarchy, your advisors should not scream incoherently; they should tell you how your subjects feel about the change under way and it's probable implications.
Incidentally, the change in attire and speech should mean that Elvis should look like a jester in a bearskin at first, and then like a classical jester wearing a tunic, and then like a medieveal clown, and then like a Victorian music hall artist, before he goes all glitzy.
I also wish they would abstain from that extremely irritating message splashed across the screen towards the end of the game: "15 turns left to the end of the game!" "14 turns left to the end of the game!" and so on. In the same vein, once the game has told you who won a game, and why, remove the message so those who want to play on for a bit longer don't have to see it all the time.
I seem to be the only one who takes an interest in this, but I really love most of the music in Civ IV, with the exception of the space age music. I'd like to hear most of it in Civ V too, though they could get rid of the banana boat song. Some shamanistic music would feel less anachronistic. There are also some songs from older incarnations of Civ that I'd enjoy to see return. There is, for example, the barbarian/Aztec theme; it could be used any time the barbarians capture a city, as it was in Civ I (and II?). Then there's that very lovely tune, "The World of Jules Verne", from one of the XP's of Civ II. And the catchy melody that always turned up for the first time in Civ III when you had reached the industrial age.
In Civ II, sometimes you (or one of the AI civs) made a scientific breakthrough and suddenly got a technology for free. Back then, it happened if someone gifted you a unit with superior technology you didn't possess. That's not a very good idea, but perhaps, in certain situations where various good points run together (they could vary but be a confluence of things such as a flourishing economy, heavy investment in science and many learned institutions, good relations with advanced countries, booming trade, extended warfare of a specialized kind) perhaps such a breakthrough could occur without upending the game.
If a civ is given units with superior technology it doesn't yet posees, it should be able to keep them unchanged but be unable to build any similar units themselves. Also, if someone gifts someone else, say, English Redcoats or French musketeers, the same thing would apply: they'd change their colours a bit but still visibly be English redcoats or French musketeers or ballista elephants and so on, witht heir particular strengths.
Finally, I think there should be mercenaries. You would have to pay for them each turn; if you don't, they desert you. They should be more expensive than normal troops, but also very, very good soldiers. (Both mounted and foot.) A limited supply of them so if you don't hire them, the likelihood is that your rivals would snap them all up. (This means that at the outset, one should be in on the bidding for them; gradually but fairly swiftly, they'd all be employed except for temporary layoffs for various reasons, such as a civ not being able to afford them any longer or ceasing to exist.)
Monetary unions as an option between two or more civs long before the UN? Any member could cancel its membership after ten turns. A war between two members of a monetary union would not affect anyone except, of course, the two nations at war.