Probably been done to death already but what I miss from Civ IV to V is the large differences the different leaders made, these were so great that they did shape the way you played (and thus the civilisation, the whole point of being a leader!). I also believe that there is scope for civilisations to develop differently to their set unique units, buildings and hex improvements (say that a Scandinavian civ started in the Sahara, why would they develop ski troops?).
Taking Civ V, this is what I would do:
1. Great people can be used to unlock unique buildings, unique tile improvements or unique units depending on the environment that your civ is based, the resources you have available etc.
e.g.
- The majority of your civ is based in or around mountains, a great engineer or merchant can unlock the terrace garden hex improvement
- You are based in largely forests, a great prophet can unlock earning faith from forests
- You have a great general but you have only used warriors and/or swordsman in any fighting therefore you are restricted to unlocking the legion unique unit
- You are based around rivers, a great engineer or artist can unlock a hanging garden building.
2. Allow stacking of units but restrict army size based on the size of the population and the resources available, you can increase your military to a high proportion of your population but this will decrease production, science etc. See 3 and 4 as to why this isn't a return to the stack of doom.
3. Units cannot heal outside of foreign territory nor can they heal in cities that have not been suppressed or are in revolt (Stalingrad anyone?)
4. Militia are a type of unit that must be built and need to be stationed in cities i.e. cities don't automatically have defence like in Civ V (yes, a return to older Civ rules), or you station other military units in cities (this also allows for blitzkrieg style invasions)
5. Cities can grow organically like in Civ V or have tiles bought but tiles can be lost to other civs with greater culture (another return to Civ IV but mixed with my favourite feature of Civ V)
6. Only scouts can cross sea and ocean without the aid of naval units (sorry but the mass exodus' available in Civ V is a stretch too far)
7. Minor civs expand and develop a lot like the barbarians do in Civ IV but you can negotiate, influence or fight them like in Civ V.
8. Bring back corruption! If you don't have rule of law or at least some national cohesion watch your civ splinter (like the Roman empire), this can be achieved with a freedom/order slider in each city with -ve and +ve aspects for each. The limits for the freedom/order balance can be dependent on what buildings you have in place and the influence other civs have on that city.
9. Bring back slavery for pre-industrial civs, this was too widespread throughout all parts of the world to ignore.
10. Have significant leader traits/bonuses that do effect how we play.
11. Get rid of Civ V's social policies and go back to Civ IV's take on them or have sliders with bonuses/negatives that increase/decrease with the more technologies you have researched.
12. Get some decent AI.