I'm not sure if this has been mentioned-and, since there's about 27 pages of posts, I don't have the time to check. But they're mostly cultural changes.
1. All the different era changes shouldn't be automatic. Instead, they should start in one city (probably the capital), and then spread to other cities, over a couple of turns. For example, when the classical age starts, instead of all the cities suddenly being torn down and being replaced with classical cities, only the capital should make the switch. A nearby city would then spend about a turn becoming classical, and then another nearby city, etc. Maybe the eras could even spread to other civs, like the renaissance did in the real world.
2. It should be possible for civs to lose technologies, in wars and riots and so on. Not all of them, but the complex, specialized techs. These would require specific buildings (usually libraries) to be recorded. If that building/library is destroyed, in a war or riot, then the tech is lost. That doesn't mean that all buildings and units that need that tech would be destroyed, but you wouldn't be able to build more of them, until the tech is rediscovered. It would also be possible to recopy techs' records in other libraries, and some future techs (like printing press, or the internet) would make the loss of a technology much less likely-but not impossible.
3. Changes of State Religions should be much more dramatic, with riots and so on. Also-and I think this has been mentioned already-but it should be possible to persecute other religions., as in expelling believers and destroying their buildings. This would make the remaining population happier and more loyal-but the extent of the destruction would depend on that religion's influence on a city.
With only 10% of a city being heretic,only temples would be destroyed. But, if 80% was heretic, not only would temples be destroyed, but some other buildings in the city would be destroyed too (which might destroy a couple of techs, as in #2). And, since so much of the city is heretic, they might rebel-and the garrison and governor might join them. which would require the army to come in, squash the rebellion, which would result in the slaughter and forced conversion of thousands, as well as even more destruction of buildings. Though I guess it would also be possible to let that city continue with their religion, which would end the rebellion.
4. Advancement should slow down sometimes. I think this might already be in the game, but I mean more than because your spending more time with taxes. I mean, if theres a war and riots and a plague and an earthquake just happened, then nobody will care about the next tech, will they? Tech advancement in such a case would take twice as long then it normally would. This should also affect other things, like construction or recruiting. Can't build a school if half the workers are sick.
5. OK, completely revolutionary idea that I'm pretty sure no one else has thought of-or at least posted. It would probably annoy a lot of people, though, so even if it were used, it probably be possible to disable it. OK. Basically, a new unit is added-you. The ruler. You would only be able to know what the ruler knows. And the ruler's knowledge of things would be limited. Because it would take so long for messengers to reach him, much of the world would be filled with outdated info, by a turn or two, usually (this would probably be shown by increasingly dark shades on the ground). Also, his orders might take a while to get to far away cities-if he'd want to build something in a different city, a messenger would automatically be sent from the capital to that city, and the construction would only begin when the messenger reached that city.
But that would cause problems. How could you run a war if all your info about the front is outdated? You would have to automate it-or move the ruler closer to the front. The ruler would be able to move to other cities whenever he'd want to (or, better to say, whenever you want him to). But, since he wouldn't be in the capital, some things would have to be disabled. If you're not in the capital, you wouldn't be able to make treaties with other nations, for example, because all the diplomats stayed in the capital. However, you'd still be able to send orders to other cities-they'd simply come from a different place. Eventually, however, with new techs like the railroad or telegraph, this distance problem would effectively disappear-to control a unit-you'd just send a telegram to the closest city, which would send a message to the unit.
5.5 OK. One small issue with that. With very large empires, it would be impractical to send messengers to faraway cities-it would just take too much time. So, you'd have the ability to set up distant provinces of a couple of cities, who would be controlled by a Governor, who would be a unit like the ruler. The governor would be more than the automated production that you could currently do in cities-the governor would also be able to move units within the province, and build roads, and mines, and so on. However, the governor wouldn't have as much power as a normal ruler-he wouldn't be able to attack or contact other civs, leave the confines of the province, or send units outside of the province, etc. The province would also remain a part of the civ, and the Ruler would still be able to mess around with the province as much as he wants-he would even be able to replace the governor. The Governor would also have a representative with the Ruler.
But, everything wouldn't always stay the same. If the Ruler never makes any orders in the province, then the province will slowly stop feeling connected with the civ as a whole, and might develop its own culture (I don't mean that the American province of California would start thinking of itself as Persia. They would just start thinking of themselves as Californians instead of Americans-though California may take on the characteristics of Persia). This culture would spread, more and more people in the province would switch to it, until you'd notice that the Governor's representative is wearing different clothes than he used to. And, since the province would become more established, they might be looking for more autonomy. It would start with little requests from the governor-that the province's units only be used for defense of the province, that the governor would have the right to set his own tax policy, that the ruler lose his power to construct in the province, etc. Eventually, the Governor would ask that his province seperates into it's own civ-whih would make it a colony or vassal state. Or, if the province/governor really doesn't like the ruler, it might just go like the US instead of Canada and declare independence. The trick to avoiding that would, of course, be to keep good relations with the province and Governor-a little gift now and then wouldn't hurt.