There are a few things I've missed and a few things I wished for.
First the missed.
I miss when other civs could be blocked by a warrior standing in the way.
I miss spies stealing tech.
I miss the Civ3 Advisors(Civ 4 substitute SUCKS!) Civ2 had the best

I miss Cruise Missles(in Civ3 I rarely used them because by the time I got them I was the last one left on that island or continent) mostly because now I try not to destroy as many people because of the Religion aspect(I can lead them into battle, and then destroy them when our enemies are crushed or converted)
I miss the old tech tree. The new one is great, but I think you should have paper before you have nukes.
I miss the change in how the leaders looked each era.
The Navalbombardment of land, and the cities naval defense.
Actual Trade routes should be neccessary again, I hate the fact my enemy is getting uranium from an island where there is no harbor, or a city completely cut off from them.
What I wish for.
CivilWar If enough people are unhappy, then Civs with more than one leaderhead should be able to split into two nations. (i dont know if it was in the first 2 civs because Civ I just pressed buttons moved troops, civ2 i did the same but kileld everyone off)
Religions should interact with eachother more. And certain civs should have preferred religions.
Edit: oh yeah.. Not to sound evil but.. Ethnic Cleanser Units. Basically, Capture an Enemy city send in an Ethnic cleanser and the city is no longer only 20% yours but now 100%, of course their civ will be angry that you have killed their people. In later years introduce a second unit of this type, to instead of killing them, deport them, and it brings it from 20% to 75%.
And another. Relgion Cleanser. If you wish to rule the world, first thing you need is followers. You control a religion and spread that religion to other countries your already starting your rule, however religions may spread to your country or your allies countrys that you don't want. Send in a religion Cleanser. Basically, it wipes out all NoneState Religion. If your the founder of the Relgion, then you maintain the right to enter any City with your religion be it your own civ and cleanse them.
Also Terrorist. You should be allowed to create terrorist or fund terrorist groups like the barbarians. it'll make the world mad at you, but itll help you.