My favorite 3.5e paladins are Eberron halfings who ride in on velociraptors. You can even take them into the dungeon.

Yup. That's why they dropped it. Sneak Attack can't replace the party cleric. Nor can Warlock's Curse. Why should a paladin's class feature?

To be fair, medium mounts can fit into a 5' wide corridor without squeezing.

Yeh it sucks, I mean now my spider obsessed player had to make his own frickin class so he could be a spider rider...

Why not just create a giant spider with a power granted to riders who have the Mounted Combat feat? A whole class or paragon path devoted to this seems excessive.

In 3.5 he had the spider rider prestige class. In 4e he wanted to replicate the abilities of his prestige class in a full blown class. It's changed a bit now but its fun to see him play something he wants to.

Uh.....anything in the MM can count as a mount, you just don't get anything special unless they have a Mount ability.

^^ read post above yours Victor, he wanted a class.

5d8+25 and some nice spells hardly made the Cleric worthless.
Clerics were one of the best freaking classes in the game, even before going out of core they made a strong case. Paladin didn't hold a candle one the Cleric got his hands on 4th level spells in 3.5, and forget about it if you used splatbooks. Retarded spells and prestige classes out the yang for clerics.
Anyhow, what was so broken by a Unicorn mount? Or the special mount, for that matter? Nothing. Not a thing. Same thing with the Leadership feat.

I'd beg to differ over Leadership. Not broken as in overpowered but broken as in destroying a great deal of the fun. Was in a high level game once where over half the characters ended up with Leadership. By the time the PC's and their cohorts were counted, we had a 9 member party. Can you say unwieldy combats? Yeah, I thought so.

You think that is bad? I was in an epic (in scale not level) game where we had 11 players around the table, each with two or three characters, half of the characters had the Leadership feat and we collected NPCs. I think at its height we controlled an army of nearly 200 with most of them having class levels.

Even with those numbers, we usually just kicked open a door, pushed the Frenzied Berserker in, clouted him on the head and slammed the door shut. The problems on the other side of the door usually went away after that.

Needless to say, that game got boring rather quickly.