Well, here's been my experience so far, using a 70 Protection Pally.
SM is pretty easy. Cathedral is easy to pull the first 2 floors before the cathedral itself, and aoe them down. Then you just go into the Cathedral itself, run straight up the middle and pull mograine, then walk backwards until you are fairly near the door, at which point everything should be nicely grouped in front of you. Target the Abbots with your melee attacks, it makes life easier. I keep up Blessing of Sanctuary, and Ret Aura. I use Seal of Light on pulls to help keep my health up, then I use seal of Wisdom once I have everything where I'm going to pull to...this helps with all the consecrations you'll be using, since Prot pallies aren't known far and wide for their mana pool.
You can do this alone, or it can be a major boon if the character you are leveling happens to be a Mage to help AOE, or a priest / paladin / shaman / druid that can heal you while you do it. It's not necessary, but it is nice.
At this point, i'm now stuck. I took this mage to 45 (go forums), but am currently having difficulty finding a good place to go. Here is what I have tried:
ZF - Terrible as a prot pally. Your choices are either kill all of the witch doctors as you go along pulling which tends to make pulls shorter and considerably smaller overall, or you can pull a huge group, and hope you can macro target the totems faster than the NPC's can lay them down. If you don't, they will pretty much get all their life back every tick. Then, of course, there is the beauty of runners...they scatter in every which direction, some of them never come back, and sometimes they just wander outside the world so you can never get out of combat, nor can you kill them. Overall, this place is a pain in the rear.
Uldaman - Same as ZF, just lower level. At 45 the xp here just didn't justify the time it took to kill, since they all drop the same totems the mobs in ZF do. Also, the pulls are annoying, and most of the mobs end up leashing.
BRD - This place isn't bad, but I can't kill enough at a time to make it really worthwhile. Even at 70, if you pull more than 10, they really chew through your HP at a decent rate, plus they have a lot of HP so they take longer to kill. In this place, like ZF or Uldaman, I'm betting it is probably faster to just have a high dps class kill singles really quickly than it is to attempt to AE, especially as a prot pally.
I'm considering Strat to try next. The mobs are all high enough level that even if they aren't elite they should still yield decent xp, plus most of them are undead, so I can put on conc aura and push out a holy wrath here and there for extra DPS. I'll try to report back after I see how that goes tomorrow.