Having been introduced to Civ2 a few months before I bought Civ3, I pretty much skipped Cheiftain and Warlord. I started my first game at Cheiftain just to get familiar with the differences. It was so easy that I quit before the end of the ancient era, and started again at Warlord. I only played a handful of games at Warlord before moving on to Regent. I played at Regent for about 6 months, and learned a lot from this site, before recently moving on to Monarch. I found the move so easy, that I took a shot at Emperor... whoops, I'm not quite ready. Anyway, I will comment on each jump in level, assuming a player with no previous Civ experience who doesn't immediately find this site for help.
Cheiftain to Warlord
This is a tough jump because if the players is comfortable with the AI's speed on Cheiftain, he may be caught off guard by the fact that the AI is nearly 67% faster on Warlord. After reading some strategy guides and getting advice from other players, this should be fairly easy to deal with.
Warlord to Regent
The player has learned a lot from forums, and wonders why he ever had any difficulty on Cheiftain. Warlord to Regent is a very narrow gap, quite possible the easiest jump. If you ever want to beat Deity, I recommend that you move to Regent as soon as possible.
Regent to Monarch
As I said above, this was a surprisingly easy jump. Being the peaceful builder type, I was far more efficient than the AI and this offset the slight production advantage given to the AI.
Monarch to Emperor
This is the first big hurdle for me. Being the peaceful builder type, my military was woefully inadequate. This move may be much easier for a warmonger. I am currently developing an early military strategy, and expect to be at least comfortable playing at Emperor by the end of January. I voted this to be the toughest.
Emperor to Deity
Yes, this is very difficult, but by the time I can consistently win on Emperor, I will probably be a full-blown warmonger throughout the ancient era and into the middle ages. While the difference between these two levels is more than twice that between Monarch and Emperor, I expect aggressive strongarm tactics and other more developed strategies will make this a little less difficult than the previous, at least for me.