The experience of leveling each of these melee classes is very different than the others. Here's my quick summary of what Blizzard got right and what went wrong in terms of the early levels.
Rogues start off well enough. One of the best changes they made is that at low level a one combo point Eviscerate hits for more than a Sinister Strike. At level three you are fighting boars by alternating Eviscerate and Sinister Strike. At seven it was two Sinister Strikes per Eviscerate. At level eight you get Ambush and everything goes pretty wonky. Ambush tends to half-kill things, so Ambush + Eviscerate and auto-attacks are all I used. Sometimes I would be waiting five seconds for stealth to cool down before proceeding to the next mob. I was having so much fun with Ambush that I picked Subtlety at level 10 and proceeded on to Loch Moden. Unfortunately I very quickly started to feel like a one-trick pony. With the early talents in Subtlety I got critical Ambushes as often as I didn't, which meant one-shotting things. When I didn't one shot things a critical Eviscerate would finish them off. When that didn't happen it was amazing how slow and painful it was to finish them off. Fighting two enemies at a time was right out of the question unless I had Evasion up, and not even that secure with it. A 70% dodge chance pretty much guarantees the win against a single guy even without getting to lead with Ambush, but the fight takes a long time and I still take a lot of damage. With Sap at level 12 I got extra flexibility in what I could do, but in Loch Modan, which is rather crowded with Troggs and Kobolds, I was dying an awful lot. Maybe this would have turned out better with Combat, but Rogues felt very weak compared to other classes for almost all applications, except for obliterating single targets for which they were grossly overpowered.
Overall Grade: D
Paladin (Blood Elf)
The Paladin was a tale of extremes. The first thing you notice when you start playing a paladin is that every time you Crusader Strike your enemy (which is every 4.5 seconds), scrolling text appears to let you know that you gained 1 Holy Power. If I were a newcomer to the game in 4.0, rather than someone who is keeping up with all the forums, then by the time I hit level 5 I would figure I had well over 100 holy power and wonder what I was supposed to do with it. When you hit level 9 you finally learn Word of Glory and get your Holy Power bar under your unit frame, plus a brief explanation of how it works. At level 8 I was struggling a lot with enemies. My damage was quite low and it took me a long time to beat things. Word of Glory solved that by healing me for more than my max health. A free max health heal every 13.5 seconds really reverses your fortunes in a lot of battles. The option to instead take a free 75% heal every 9 seconds is handy too. So at level 9 I became totally invincible, but it was still slow to kill enemies. This might be because of the selection of weapons available to me from starting quests (no two-handed weapons from early quests). Since I was using a one handed weapon and shield at level 10 I figured I'd give protection a try rather than go with the obvious Retribution. Protection is an insane mess. I was fighting enemies with around 160-180 health. My Crusader Strike hit for 15-19. My Avengers shield hit for 150-160. I would gather three guys up and one shot them all with the shield, or at least leave them one auto-attack from death. If I got too many guys by accident I always had my instant cast, free, full heals to fall back on. Basically I was invincible, had a 24 second cooldown on my instant-cast three-target instant-death spell, and otherwise was nearly useless. After shaking my head at this for a bit I switched to retribution (only a 17s respec fee!) and tried that out. I ended up still using a one-hander because I got a green from a quest that had significantly more dps than any two-hander I could find. Templar's Verdict was pretty disappointing, doing only a little more damage than Crusader Strike with three holy power (I don't understand why or how, but that's what happened) and so I mostly just stuck with my Words of Glory and hitting people. My damage was quite a bit higher and I didn't have a move that did 90% of my enemies' health on a long cooldown so the game played a lot better. Still, being relatively low damage and at the same time completely invincible is not compelling gameplay. I have to admit that this experience probably would have been greatly improved by simply changing some quest rewards.
Overall Grade: C (if I was grading Prot, I would give it an F)
Warriors begin with a new ability called Strike. It costs 20 rage and makes you hit your enemy. It also shares a cooldown with Bloodthirst, Mortal Strike and Shield Slam, so you retire it immediately at level 10. This is a really good idea and solves a problem that exists with several other classes. Warriors are supposed to have a hard-hitting ability to dump their rage into, but the ability they get is chosen by their talent spec. Similarly, paladins are supposed to have a Holy Power dump, but their primary Holy Power dump is chosen by their talent spec. For warriors, the solution was to give you a low level hold-over ability. For paladins, I don't know that any solution was even contemplated.
At level three warriors get charge and at level five they get Victory Rush. Victory Rush now heals you for a significant percentage of your maximum health so you can happily run from enemy to enemy and fight away. Of course at low level health regenerates so fast out of combat this doesn't matter at all, but it was pretty great for getting me through a fight with two enemies, especially when extra enemies added in midway through the fight. Rend has been improved in that it appears to get a tick immediately when applied. This made it useful when first learned even though enemies generally die pretty quickly at level seven. With charge keeping me moving and three different buttons that I actively used in combat, low level warriors are fairly simple, but not boring to play. There is some optimization to do in your button presses, but anyone who just hit their buttons would beat enemies at low level. I had just picked up a couple of one-handed weapons from quests with no two-handed alternative, so at level 10 I chose Fury. Bloodthirst did about 30% more damage than Strike, which seemed like a nice trade-up, but not fundamentally game changing. The small amount of healing from it also helped when I got in difficult situations. Usually I felt a little bit invincible because Victory Rush healing made it so I could beat an unlimited number of enemies in a row. But if I hadn't been careful in the Furbolg cave I easily could have engaged too many Owlbeasts at the same time and died. Every ability seemed to fit its niche very well. Thunderclap, for example, did enough damage that it was worth it to hit it when I was fighting more than one thing, but not worth hitting against one enemy.
Oh, and I don't know how long it's been this way, but they removed the damage penalty from Titan's Grip. I am thrilled.
Overall Grade: A