Story wise i can't really tell, i personally thought both stories weren't that interesting.
Paladins are the defensive tanks and are easier to play for their rotation is really simple compared to warrior. They also have a lot of skills which boosts your defense or reduces damage taken. Paladin is pretty much focused on lowering the damage taken, while warrior restores HP after they have taken a hit. Warriors are the offensive tanks, they can dish out a nice amount of damage but are harder to play in general. Some of their buffs and stuff are based on your damage done, (damage to HP etc). Both are useful, both are used in endgame raids so it doesn't really matter what you pick. I'd just go with whatever you like more. If you're going for warrior, you will still have to level your gladiator to level 22, cause provoke is a must.