I've played both up to the 60s, at least. My paladin is higher but I gave up on my warrior somewhere in Ungoro Crater.
I can this about those levels. Paladin is MUCH easier to level. A quest that comes to mind is the one at the dwarven quarry where you have to go in the cave. With my warrior, I almost couldn't use charge because I'd get 2 or 3 more adds and I'd die. I was shotgun pulling and killing them one at a time. Ugh! With the paladin, I'd run in and judge light and call it a day. 2, 3, 4? Who cares? I'm getting healed with every hit and have back up heals in case things get crazy.
Wait until you get to 20 to compare. Tank Deadmines and see which one you prefer. That's not the best case scenario, but it's better than working up to 80 to find you don't like it. With a paladin tank, you'll be running into packs of mobs and consecrating to keep aggro. You'll generally live through it okay and keep your party safe. You'll have a couple of buffs to throw to people and a bubble to save a caster if you need it.
With the warrior, you'll have a plethora of buttons to mash - none of which will hold aggro on more than one mob. Sure, there's thunderclap and cleave but if a dps so much as sneezes at the wrong mob he'll pull aggro. On the plus side, you'll have shield block which pretty much makes you immortal every 45 seconds or whatever. It'll be fun to pull a pack of mobs, pop shield wall, and watch every attack be blocked. Then you'll try to hold aggro and lose it. Then you'll run around taunting and praying you get enough rage to throw a sunder armor on the mob attack your healer.
"Feel the fury of the mountain!" ~ King Magni Bronzebeard, Lord of Ironforge