Im a bit late with my reply, but its better ever than never.
Im playing holy pala for 3 years now, started from level 10, without any BoAs (my first charr on account. After gearing him and raiding on him, i rolled Enhance shaman who ended up (surprise! Resto), also riding geared. After him, i started Druid, YEY! another healer
I dont like playing clothers, so i skipped Priest.
Now, these are my 2c.
Holy paladin - best tank healer. period. There is noone close to it, insta free heals, huge hits if farget is below 35%.. everything there just screams "Tank, your ass is mine!"
Resto Shaman - Oh man... most fun to play and hard to master, hands down. in 4.3 with few talent changes they can easily go from formidable singe target healer to AoE healer. Lots and lots of utility and nice combo of casted heals and HoTs.
Resto druid - Most unusual to play, and pretty much decent to master. Not so good single target healers as shamans (cause they dont have that choice of talents) but outstanding AoE heals. Lots of stuff to monitor.
This all changed with patch 5.0.4 - Palading became pretty good AoE healers too, and even better tank healers with Sacred Shield or 3 hoiy power Eternal Flame HoT. Lvl 90 talents are also good, giving us a option of even better tank healer with another HoT, or one more AoE HoT healing. I didnt have a chance to try rest of my classes, but what i can tell you is that Druid resto (tree) form is back as perma shapeshift, not as it was in Cata.
I will prolly roll a monk for sure, and for sure it will be my main. I have played it on beta to learn class and mechanic and i can telly you that they are perfect. I can openly claim that from all changes to old and 3 new specs in new class, Monk, Mistweaver (healing spec) got all the love, there is a ton of synergy between spells, you can easily switch from Single target to AoE healing and utility with Mana Tea (restores 4% of mana with every stack of mana tea, channeled 1s per stack. Braking channeling does not consume rest of Tea stacks).
Tbh, by looking at healer monk spells, you will see a mixture of all good spells that other healing specs have, combine that with King-fu panda.. and well.. what is there not to love?