My list: (apart from the AI improvements)
Minor:
Puppet states increasing the Social Policy cost
Improved Mines (+1P with Dynamite?)
Mounted unit penalty for attacking cities
Two non-combat units per tile (only-one-can-work is fine)
Major:
Rampant unhappiness causing puppet states to become new city-states. (With initial diplomatic relations based on how much unhappiness)
The last one is a big deal: it's what I've wanted in all of my Civ games, and Civ 5 comes the closest to implementing it. The history of the world is full of large empires fracturing and splintering. I want to see colonies revolting and civil wars occurring, without it feeling like I'm 'losing' when it happens.
If my people are minorly unhappy, then a fringe city splitting off into an friendly city-state doesn't seem that horrible. It helps fix my unhappiness problem, and seems like a reasonable trade-off. I can ally with them, or conquer them, or ignore them. I lose some science/income/control, but that's fair...I didn't have means to manage it.
If my people are majorly unhappy, then a fringe city splitting off into a city-state that is at war with me also seems appropriate. If my leadership is that awful, I should be expecting civil wars.