Onto a controversial topic: Shamans vs Paladins, which one is better? I've never played a shaman to any significant level, only fought against them in PvP, so my impressions of them may be flawed.
In PvE, my thoughts on which are better is a bit complicated. I think a group with paladins is better than a group with shamans. Most people would agree, and say it is because paladin buffs cover the entire raid, while shaman buffs only cover the group. I don't think this is true though. A normal 40-man Alliance raid gets 200 person-buffs (5 paladins x 40 people). A normal Horde raid gets 100 person-buffs (5 shamans x 5 people in party x 4 totems). So on a strict level, shamans give about half the buffs of paladins. However, shamans have far more flexibility with buffs. I believe that they have 16 different totems to chose from. In contrast, paladins only have 6 (and 2 of them are talents). Additionally, the tactical blessings erase the raid blessings, so they are rarely used.
The lower number of buffs is the price the shamans pay for flexibility. I actually think that in terms of number of buffs, Horde and Alliance are reasonably balanced. Alliance covers more people, but with limited choice. Horde covers less people, but has a lot more options available.
In my opinion, the reason an Alliance raid is stronger is because a single Blessing, Blessing of Salvation, is overpowered. Salvation basically allows the Alliance dps and healers to do 20-40% more damage or healing than the Horde equivalent, or never worry about pulling aggro. Quite honestly, Salvation spoils the Alliance. I find that Horde warriors and dps are far more tuned to the nuances of aggro. In fact, I think if you removed Salvation (and Tranquil Air Totem), an Alliance raid would be significantly underpowered compared to a Horde raid.
(As an aside, you often see Horde complaining on the message boards about Blessing of Kings, which amuses me. If you ranked the Blessings in order of importance, Kings is #4 behind Salvation, Wisdom, and Might. It's really only good for tanks, and while it's a strong Blessing, it's not necessary in the same manner as Salvation.)
In PvP, on the other hand, I think shamans are clearly more powerful. They do significant damage, and have a lot more options than a paladin does. Their greatest strength, however, is their mobility. This includes effects like Earthbind Totem. A good shaman has a lot more options that allow them to control the battlefield. The shaman's advantage in PvP is the fact that she has a wide variety of tools. The paladin's advantage is her survivability. A paladin has a few very powerful tools on long cooldowns. A Hammer of Justice may be strictly better than a Shock, but HoJ is once a minute and there is a choice of 3 different Shocks available every 6s.
In my opinion, mobility and flexibility trump survivability and rare powerful effects, especially in games with 30s ressurrection timers. The fact that a shaman can do more damage than a paladin is not what makes her superior. It is the arsenal of options available to a shaman that gives her power.
Comments from any shaman readers are appreciated.