I'm somewhat curious about that statement; I recently upgraded to King from Prince and to me, the difficulty didn't seem to increase at all. I played four games (Denmark, Maya, Poland, Ethiopia, in that order) and none of them were any problem at all. I got less wonders than usual and I had to fight a few more wars, but overall, I didn't really notice the increase in difficulty. Admittedly, I lost the fifth game I tried, but if you start right next to the Huns and don't build up your military early, you get what you deserve. So that one was completely my own fault and had nothing to do with difficulty.
So what I'm asking is, is Emperor really not much more difficult than Prince even?
For me (and it seems many others):
Prince->King: quite noticeable. Prince level means that the AI has insignificant bonuses which can't come close to the major human advantage of free will. Prince->King is the jump when the game becomes less about fantasy role-playing and more about the strategy of your choices
King->Emporer: not noticeable. The small advantages that Emporer AI has over King AI is not significant enough for the player to notice. Haven't played at this level in a while, but I imagine all King-pertinent strategies are directly applicable to Emporer and vice-versa.
Emporer->Immortal: a big change but something that you've already learned to compensate for. One of the big adjustments made from Prince to King is learning how to compensate for not having wonder bonuses and setting up your core cities earlier. Having already learned this, you're ready for Immortal. The big difference between emporer and immortal is that the AI's bonuses on immortal allow them to jump ahead of you a little bit, and that can be scary if you're used to being the most powerful all game, but using the tricks on this forum will allow you to leap ahead during the renaissance era and run the game as you see fit from there on.
Immortal->Deity: massively different, may as well be a different game (Civilization5.1; Masochism and fear of the next turn button) Immortal prepared you for dealing with a brief period when other civs were ahead of you; in deity this is going to be the case for the entire game. Deity is about being the last-placed civ being the first to acheive a victory condition. Each AI starts out with several additional units, including a worker and a second settler from turn 0 as well as 4 free techs including one second tier ancient era tech (the wheel). Even more intimidating is the deity-level Liberty AI... AI (regardless of difficulty level) play the game at cheiftain level rules, which means they get a higher base happiness and an extra happy per luxury resource. This means that the main reason why human players need to put a low celing on their number of cities is considerably less of an issue for the AI regardless of difficulty level. Deity AI using liberty starts with 2 free cities, gets a third from an SP, and has a bonus to building settlers IN ADDITION to a deity AI production bonus, meaning that they can spit out cities as soon as they uncover the spot for it. When this expansion
capability is applied with less expansion
cost to a civ that's programmed with expansion
tendencies, you get Deity AI Hiawatha with 14 cities in the first 150 turns spitting out 5 or 6 units every turn. Not only do they make units faster than you can make units, they make units faster than you can eliminate their units.
The way that I tested whether or not I was ready to advance a difficulty level:
Play a civilization that's designed for a specific victory condition aiming for a different victory condition (example: Brazil for anything other than tourism victory, say domination) on a map that they aren't well suited for (put Brazil on a donut map where there's no jungles) and hand-pick AI's that are good at stifling that victory condition (for difficult domination AI's, don't just include Shaka, Genghis, Attila and all the warmongerers because they make it difficult to overcome their large armies, but also include Pocatello and Sejong who will actually try to win the game via other methods while you're dealing with the warmongerers. Complete this task and you're ready to move up a difficulty levle.