Paladin = Purely mitigation. Rotates cooldowns to keep damage to a minimum.
Warrior = Self healing. Takes the big damage with a huge HP pool and heals a good amount of it back by him/herself.

Paladin (as of 2.0) is the superior tank in Coil. But don't let that scare you away from Warrior, as not only are they getting buffed in 2.1 they're also really good in all content currently in the game (including Coil!). I'd recommend leveling Marauder to 30 and see how you feel about them from there. Warrior is a lot of fun, but Paladin is always effective. It just comes down to personal taste and what you feel suits you best.

The reason why Warrior struggles in Coil is simply because that description I gave of the class isn't entirely accurate. Sometimes WAR will heal a good amount back... but only sometimes. Other times you'll be struggling to keep your healers from having panic attacks. It can get quite hectic but it'll teach you a lot about tanking in FF14. PLD honestly feels like I'm AFK after leveling WAR. But some people like that... and I love it for WP/AK runs. :P