To give a perspective from the other end of the spectrum on both the initial question and the ensuing argument, I've played deity exclusively for the past year. I lose far more often than I win, but I find it fun to be forced to work out new strategies.
(...)
Its almost a different game at different levels, and I think by getting better at one level you automatically get weaker at others because a key factor is knowing precisely what is or isnt possible. I couldnt tell you if its possible to found a religion, found a second city and build the pyramids in an emperor level game - I wouldnt risk it, and would probably play far less efficiently than someone used to playing that level.
this is so true, that I had a hard time playing down from my usual monarch level to chieftain (was willing to trade, but those AIs had nothing to sell

)
I think though that the assumption that easier= more fun isnt true. Some of us have more fun losing. I'll often give up on games where i'm sure i'll win, whereas I'll doggedly play games to the bitter end when i'm losing, because you dont invent a new gambit or strategy when you're 10 techs ahead of the nearest rival..
Here you point out something else. This is what I understood as the reason for this thread.
What is fun for players?
1) Some want to learn strats, improve on them and achieve a victory over themselves, the AI isn't really relevant. This is what I understand form your post, Phyacis.
2) Others want to learn strats to improve their skills, to achieve victory over the AIs on the highest possible level. It's very close to 1), but playing at a level where you don't win isn't relevant. This is somewhat what Aelf explained.
3) Others just want to win. Skill isn't relevant. If they improve their strats, they'll move up a level. If they don't, they'll stay at a level where they can win easily. Their ego is better flattered by an easy win than by beating a tough challenge once in a while. I didn't identify someone specifically there, but I could be there, if I wasn't in the next paragraph

4) Others want to see all there is to see in the game. Different maps, different leaders, different winning conditions. The "challenge" here isn't in the difficulty but in trying everything. Mice somehow explained this. I'm here too. So I won every victory condition at least once. I played on every map type. I played every leader (not catherine, because so many people played her it wasn't really "new" to me), tried loads of exotic moves...
What is fun to me?
Vanilla monarch gives me an easy enough game to play just like I want to, but there isn't much left to explore in vanilla

. I didn't move up to emperor (played it once, but felt more like work than like game

)
Warlords 2.08 is different. I play monarch, but cannot play the way I want.
I can only win cultural or domination (no brainer victory conditions for me, I could win those playing with my feet, I think), and any exotic move is punished by being so far behind in techs that nothing can save me

.
I started prince level games, and even there I feel too much pressure from my neighbours, forcing me to play for domination.
I don't brag much about my skills (monarch is not really high level on this forum!), but going back to noble is really a hit to my ego...