First: people thinking the paladin is boring applies mainly to solo/small groups. When soloing, a paladin does almost nothing but hit Holy Strike (which has a long recast) and basic attacks, pausing to heal once in a while. The paladin is hard as a rock with heavy armor, high hit points, healing, and some dirty tricks, but as far as actual ways to kill monsters they don't have much and their damage is low. When you've got more people around, the paladin kicks up the action a bit. That's where seals come in. These are short-lived buffs, and you can have one per party member. However, useful though these may be, most last between 30 seconds and a minute, meaning lots of recasts. Some people find them more trouble than they're worth.
To sum up: paladins are strong because they're very difficult to drag down. But just being able to take damage isn't appealing to everyone.
I believe (and someone correct me if I'm wrong) that they recently changed First Aid to interrupt if the recipient OR the caster was it. Meaning First Aid is mostly downtime reduction, like food, solo or duo. Once you get 3 or 4 people it gets better, but solo or duo it's mostly downtime reduction. Even so, that's not the same as worthless. You don't have to have a healer between the two of you, you just need to have a keener understanding of what you can handle.
Not all the magic classes have healing per se. Warlocks can produce healthstones, which work like potions. Mages summon food. Hunters can only heal their pets (though hunters are really hybrids). Shaman, druids, paladins, and priests can all heal, to varying degrees of effectiveness. If, by "magic classes" you mean cloth-wearers, then it's as follows: priest yes, warlock sort-of, mage not really.
Warlocks can nuke, it's just not the focus of their skills. Warlocks are a sustained DPS class, using an array of damage-over-time spells and their pet's damage to grind monsters into oblivion with a minimum of downtime. That's the theory. If you want a nuker, I forgot about the shadow priest, but they seem to be pretty good at that... not to the level a mage or warlock can reach, perhaps, but definitely up there. Plus the priest can always heal.
Hey, answering questions isn't that bad, and your questions are more focused than some of the people on this board.