Personally it all depends. If you want to be a good caster pally, able to use seals and blessings and healing more efficiently and without worrying about mana you should go Blood Elf. Human pallies have less mana but more hp, so it kinda makes up for that. I have a BE pally, he is awesome, for the BE pally quests gets me really cool weapons like Sin'dorei Warblade and Blood-Tempered Ranseur. Also, the lvl 60 BE pally quest mount is Red and Black, i think its better than Human's Blue and Gold.
Paladins are very hated, for they are truly annoying damage dealers who can survive almost anything.
These servrs are a little less harsh towards us paladins:
Stormrage, Bloodhoof, The Underbog.
I know because ive tried em out.