I always say go with whichever one you have the most fun with.
I have both a paladin and a priest... Obviously I play my priest more.
A paladin has to hard cast stronger heals, while I can penance or bubble in an emergency(small cd). Over time, they put out more/stronger heals, have BOP and LOH. Not to mention the fact that whenever they heal anything else, they heal themselves for quite a bit. When a rogue or two gets on a priest, it can in a sense interrupt what they're doing in order to heal themselves, when a paladin would not need to do this as much because of the self heals generated by healing another target.
A priest can DPS more which is important in some situations when you need to play offensively.. Paladins cannot do this as well as priests. If you get in a bad position, the paladin has the better instant heals to get out + BOP, a priest only has bubble + renew and will have to balance between hard casting heals and moving.
In a pug, I would say Paladins are stronger because of their stronger heals, major cooldowns, mana efficiency and durability. From a fun sense, whenever you are bored you can always FC or go Ret. Go paladin if you want the stronger class. Priest has its own strengths and CAN effectively solo heal.. But is better to complement with another healer. Just be aware that paladins can be less forgiving if you don't pay attention and preheal properly.
That being said I love my priest <3. Enjoy your paladin.
