Basically you are looking at complete opposites here, priests are clothies with a lot of spells, healing and shadow magic, extremely fun to play and extremely wanted in groups, no matter what spec you are.
If you level shadow and grab spirit as your primary stat, you will literally never have to drink, MAYBE if you grab too many mobs, but just that.
A warrior is completely different, they are heavy damage mitigators(sp?)/Dealers but they are 100% melee damage and wear heavy armor.
If you go protection spec once you are above lvl 65 you will be extremely wanted in parties, because you will be an amazing tank.
IMHO, like the above poster said, level both to 20-25 and then decide.