WAR or PLD?

[Seiryuukishi]

I have both and have ran both extensively. My personal preference is paladin. However, this is about which might work for you.

Truth be told Paladin doesn't really get "good" until level 40 when you get Shield Oath. Why it wasn't 30 at unlock is beyond me, still, paladin mitigation is off the charts if you do it right. But it suffers from an lack of dps even in Sword Oath. They do have benefit of being more TP efficient if you weave Circle of Scorn, Spirits Within and Flash into the mix. Plus cross class from conjurer is useful solo.

Warrior is essentially everything paladin isn't. Their mitigation isn't great but useful in a pinch one being reliant on five stacks of wrath the other is the last skill of a combo. Dps, even in Defiance, is greater than paladin's for certain. Health is higher but that is sort of its own kind of mitigation. Cross class is lack luster at best save for a couple of gladiator abilities you need (flash and provoke). They eat TP like candy.

As far as aggro gaining and maintaining Warrior has the easier time of it especially where multiples are concerned. But you'll burn through an ungodly amount of TP to hold it. Paladins are great at single target. Bosses are a great example of this because they can hold out in a pinch due to their mitigation to give healers a quick break to heal party. A lot of their issue with multiple target aggro is that their only true multi target gainer is flash where warriors get flash (if cross classed) steel cyclone and overpower. Unless you are spamming the crap out of flash at the end of your rage of halone combos on top of circle of scorn every time its up you'll pull your hair out trying to keep it off of the party especially if you have black mages.

Story is best left for you to decide. Ultimately I'd say level them both and get a feel of them. Then pick what suits you and your play style.