A regenerate map button in the menu.
A clock (I know there is a mod for this, but COME ON!...that was one of the smartest things they added in 4 and they take it out?)
Map trading...Really Firaxis? I am one of those OCD people who need to see as much of the map as possible and not having this makes it just that much longer before I can see the entire world as a whole. Plus I looked around for 10 minutes in the Civilopedia til I realized that it just wasn't in the game.
Amen! A simple clock with an alarm that I can use without modding and losing my achievements! Geez, is that asking too much?
A palace to create! Not essential to the game, but still fun.
Actually seeing all the buildings in a city, not just the wonders. Watching a city grow in cIV was a nice aspect of the previous game.
City health. Leave happiness as it is if you must, but bring back individual city health. Give us a real reason to go after the bonus resources again.
Airlifting units. Forcing us to embark every unit going between diffrent coastlines becomes really tedious, espically in the modern era. We do have ariplanes right? Or are they strictly just used for killing in the Civilization universe.
Adjustable tax rate. Real life governments increase taxes all the time, why can't we?
Random Events, Forests Regrowing, I do miss Religion, Wild Animals, I could go on and on about all the "little" things missing from ciV that I miss.