Based on previous experience, my opinion is:
PvP Retri/Protect/Preg - human (a no-brainer especially when P3 hits)
PvP Holy - this one is tricky, having two trinkets is incredibly useful when you find yourself in mana wars against a resto druid. On the other hand, vast majority of Holy paladins will play with a Warrior in 2s and with Ele Shaman + Destro Lock in 3s. None of these have a silence, so an extra CC that is different school than all hard CCs can come extremely handy. My verdict would be human anyways, because your partners - human Warriors and Warlocks, are stronger as humans than as any of the horde races.
PvE Retri - none of the two has significant advantages
PvE protect - none of the two has significant advantages
PvE holy - blood elf (a no-brainer since standard PvE holy paladins are usually built around stacking as much mana via intellect as possible)