As background, I played WoW quite a bit in Vanilla, but lost interest quickly once BC came out and rendered all my 1337 PvP gear obsolete. I remember Paladins being a holy terror in PvP! (See what I did there?

I even leveled an alt up to 40 or so way back when and I was shocked at the situations I could get into and live. I was straight out of EQ at the time, so my ideas on what I could and couldn't do in an MMO with a toon were a bit skewed.
So anyways, I hear Paladin DPS sucks, they're only good for heals in end-game content, no one wants them for pre-made PvP groups, they make squishy tanks, and leveling takes forever. Really? Either I'm not remembering things correctly, this ain't Vanilla, or people aren't doing something right! I'm open to any of the above options. I realize my memory isn't what it used to be...
Admittedly, I've only raided in WoW a couple of times as a Tauren Hunter - as I hated raiding from EQ - but the rest of it seems to differ from what I remember. So I can't speak for the end game content with personal experience. As for the rest:
Low DPS: Of course Paladins won't have as high as a Rogue or Hunter with all the other cool toys Paladins have. I would think they have plenty enough to level and pull their weight in groups.
Leveling: Not dying anywhere near as often means less CR's and buffing and more killing. That alone should mitigate a lot of the lower DPS issues.
PvP: With the ability to not die, remove snares, heal, stun, bubble, and still throw out decent DPS, I don't see why they would be frowned upon in pre-mades.
Tanking: Plate mail, healing, stuns, adequate DPS, bubbling... Sounds good to me.
Again, I fully admit to only actually playing a Paladin to level 40 or so on Live, so my first-hand experience is limited and foggy from the years. So where is my logic going wrong here?