No Religions
Religions weren't necessary, but it added flavors to the game. It was awesome trying to spread your state religion to the whole world, earning diplomatic favors and gold in the process. CIV IV lovers want the religion system to enhance so that it can impact the game in a more meaningful way, not remove it entirely.
No Espionage
Espionage was one of the best features to have been introduced in the CIV series. It gave players so many options and alternatives to go against their opponents without the risks of declaring open war: poison their water supply, scout out enemy troop strength, stir up a rebellion, steal their treasury, sabotage their wonder construction, etc. Why is this awesome feature removed completely?
No Civics
Civics was another extremely well-thought out feature that was added in CIV IV. Not only did it add flavors to each nation (Communism vs. Capitalism, Emancipation vs. Slavery, Universal Suffrage vs. Police State), it provides long term tactical options as well as short term flexibility to players to adapt their empires based on the current circumstance. Deciding and changing Civics was always a weighty decision because each one of them have their pros and cons. It makes each nation unique because rarely do two empires have the identical set of Civics.
In CIV 5 Civics are replaced by Social Policies, which is fundamentally a ladder of perks with bonuses that you can upgrade one at a time. It may still be strategic to decide on which branch of policies and perk to upgrade, but because of the fact that they are permanent and you cannot change them, they offer absolutely no tactical flexibility to players. All branches and perks add some kind of bonus to your empire with no negative side effects, so the decision of choosing which one to upgrade also becomes less significant.
No Hamlets
Hamlets was an important tile improvement in CIV IV as the primary commerce provider. But its greatest strength is that over time it evolves into a cottage, a village and ultimately a town, encouraging players to build them early to reap the benefits.
In CIV 5 hamlet is replaced by "trading post" which has a MUCH uglier model and does not evolve.
No Commerce, Research and Culture Sliders
Commerce, Research and Culture used to be interlinked in building your empire. Any of these resources can be distributed freely using sliders to let players develop their nations in the exact way they want.
In CIV 5, commerce, research and culture are completely separate entities. And the only decision players can make is to decide how much of each resource to produce.
No Random Events
Random events provide small bonuses and surprises to your nation in the way of additional income, one additional food resource, increased culture, etc. Those bonuses are no way game-breaking, but they make you smile every now and then and make your empire feel like a real nation inhabited by living breathing people rather than some numbers and data on the screen.
User Interface
Firaxis might have thought that they were very clever in making the UI much more streamlined and linear, but it is NOT! This type of UI may have been ideal for the console version of Civ because of the limitation of the controller, but for a PC CIV this kind of UI brings more inconvenience and frustrations than otherwise.
PC gamers want data and information easily accessible, laid out clearly right in front of them, instead of clicking through menus and menus before finding out what they want to know.
City States
I really question the point of implementing City States. It may be fun to interact with them and build a good diplomatic relationship with them, but more often than not it's much easier, simpler and faster to just conquer them and take their resources than to waste gold buying their friendship.
The importance of City States as allies in war times is extremely limited too, considering that now military units cannot stack, and City States have such a small territory, their army size and strength naturally become very restricted.
No Leader Personality Traits
It provides a historical and semi-realistic flavors to each leader. And although some traits provokes controversies and debates amongst historians for their accuracy, it's part of the fun too.