Just came in to say a pally is a good choice - they’re popular. My main’s a rogue and it’s a chore trying to get a healer and a tank (in that order).
If you’re going to play a pally, you might as well wait for the expansion so you can play a blood elf pally. That way you won’t have to hang around with a bunch of wussy alliance. 