Resto Pros: Mana Tide Totem, Lesser Healing Wave is fast and relatively powerful, talents can speed up plain Healing Wave, buff totems to give pala Windfury or Hunters Grace of Air, Fire ele for dps help and Earth ele for tank help
Resto Cons: Totems inflexible, re-cast every move, short-timed/extra burden on an already complicated multi-box healer, Mail itemization is there for healing but not as commonly as cloth is, and Priest spirit regen if done right can sometimes outweigh mana spring/tide, Tranquil Air would be detrimental to the Paladin despite helping shaman/hunters

Priest Pros: PW:Shield, aoe fear for emergencies, FADE, FORT, if alliance = Draenei Priest Racial that gives the entire party some Mana back every few mins(And Pala Tanks need their mana), and solidly-powerful heals, can MC if the right opportunity presents itself(and you can save his high-aggro ass post-MC)
Priest Cons: Squishier, requires a little more micro/hotkeys than a shaman might; MC generates a fuckload of hate in general and will take some work by the pala to regain if done

Tough choice really...I think I'd lean more towards the Priest though, if geared right their mana can last forever or not even have to drink in some cases(my old guild leader had insane regen, never had to drink in any lv70 instance, had tons more mana/lasted longer before oom than other priests/healers in raids; since your tank is a Pala, pw:shield is awesome and doesn't ragestarve him, and fearing mobs doesn't reduce his rage-income. Consider a holy pala though...

Pala Pros: Extra bubble/DI, extra blessing, extra aura, extra LoH, still fairly mana efficient like the shaman, can wear plate and there's a fair amount of pala plate out there, free lv40 mount lol, extra Judgement if you can manage it, and an extra single target 6sec stun(Blessing of Wisdom AND Light, anyone?)
Pala Cons: Likely to go oom on longer fights, flash of light not always that hot(Though Blessing of Light helps that), pretty much just a healer with little in the way of CCs or other assistance