Disclaimer: I main Paladin. I also try to be reasonable.
"Use small minions? They can counter that."
Well, yes. So does Hunter with Explosive Trap. Or Druid/Warlock/Shaman/Mage/Priest with their AoE. Rogue has Fan of Knives, which is not THAT good, but still is something. Only Warrior doesn't have AoE removal though. (I don't think Whirlwind can be considered removal...)
"Use strong minions? They can counter that."
Yes, Pallies can use Blessing of Kings on a recruit and smash a 5-health creature. Or use Hammer of Wrath. Or use Peacekeeper's Battlecry. Holy Wrath is also available, yes, but it's kinda unreliable. Truesilver Champion is a very strong card, i'll give you that.
There's also the divine shield thing, that can be frustrating to play against, but then again, divine shield isn't exclusive to Pallies.
"Use spells? They can counter that. "
Care to give some examples?
"Try to outlast them? Nope, ridiculously overpowered cards in every area, good luck surviving."
I assume you are talking about healing cards such as Holy Light, Guardian of Kings and Lay on Hands. Well, consider the fact that Pallies use (or should use) Truesilver as creature removal and the healing cards make sense. Holy Light kinda sucks, maybe the other 2 they are a bit too strong, dunno.
"All of their cards are extremely mana efficient, or very cost effective, however you want to say it"
Have to agree with you on this one, can't think of any Paladin card which isn't cost-efficient. Let me just remind you that class-specific cards are stronger than neutral cards, which sounds right.
"See a paladin in an arena? May as well auto-concede"
That's just plain stupidity. By auto-conceding, you will NEVER learn how to win against them. Reminds me of the players who said they auto-conceded against Priests because "they're OP".
"Think you've got board control? Nope, they're better at everything."
Exactly how? You realize we don't have hard removal like Hex/Polymorph/Assassinate/Naturalize? Sure, there's Equality/Consecration, but come on. How often do you see people using it? I've seen people using Wild Pyromancer + Equality way more often that Equality Consecration.
"Even IF you think they're "balanced" there is absolutely no denying they're a bunch of frustrating, anti-fun jerks"
Freeze Mages? I-Haz-All-Da-Removal-And-Extra-Cards Priests? Explosive Shot+Gladiator's Bow+Traps, Traps Everywhere+Eaglehorn Bow's Control Hunter?
Pallies are the frustrating to play against, anti-fun jerks?
"I've had enough of them, as well as the entire playerbase that DOESN'T play paladin as their "main class." "
Oh really? Proof?
"Even if they're not directly "nerfed" something needs to be done to make them less of an aggrovation, and waste of time to fight."
Pointing that out and not giving examples? Surely you can think of something?