Lots of gamers make the claim that the paladin class, first introduced to OD&D in Supplement I, doesn't fit well with the other classes. While I certainly see the logic of this claim, it's not one I share. I consider the paladin's pedigree in the game at least as solid as that of the thief and since, as I've discovered, a great many gamers will defend to the death the sanctity of the thief as a "core" class of the game, I think I'm on pretty solid ground here.
Now, it's true that, if one is going to treat Dungeons & Dragons as solely a product of gritty swords-and-sorcery, there's not much precedent for the class. For all my championing of the pulp fantasy roots of the game, even I don't argue that S&S is the only influence on OD&D. From the beginning, D&D's been assimilating all kinds of imaginative literature, to the betterment of the game's "DNA," in my opinion. It's a stronger game for having a more diverse genetic background, although that does sometimes mean its various parts don't always interact well with one another.
The paladin is a good case in point. The uptight, "do-gooder" image of the class is at odds with the way most D&D characters are played. That's part of why I suspect the class has a "bad reputation" with many gamers: a paladin in the party cramps their style. And of course playing a paladin properly is quite difficult, particularly if the referee is going to be a stickler when interpreting the lawful goodness of the character's actions.
My Dwimmermount campaign takes most of its cues from swords-and-sorcery literature. On first blush, paladins wouldn't seem to have a place in the setting. In actual fact, as my players are about to discover, paladins played a key role in the setting's history by spearheading many of the rebellions that overthrew the Termaxian-dominated Thulian empire. The Thulians had a state religion -- the Great Church -- made up of the temples of all the Lawful deities. That religion was subverted by the Termaxians once they rose to power, as Turms Termax had no clerics of his own. Instead, clerics of other gods were devoted to their own gods as aspects of Turms. In this way, the whole Great Church came to serve the cult of the Man-Become-God.
Paladins serve no known god. Indeed, they generally consider all gods to be, at best, merely powerful otherworldly beings and, at worst, demons masquerading as divinities. Paladins serve only Law, which they consider synonymous with Goodness. They take particularly umbrage at gods who claim to be Lawful and yet subvert Law for evil ends, like Typhon. Paladins travel the world singly or in pairs, spreading their particular interpretation of Law and rooting out cults devoted to Turms Termax, which they consider particularly dangerous, moreso even than the temple of Typhon. Interestingly, paladin do not shun those who do not share their beliefs, even Termaxians. Instead, they seek them out and often join their adventuring parties, hoping to use their unique abilities and charisma to sway the wayward to their cause.
No one knows where paladins come from, although rumors persist of a hidden fortress called simply "The Palace," from which they are sent out into the world. Likewise, paladinhood is not something one can aspire to; it is simply something one is. These facts, coupled with their penchant for traveling incognito makes paladins a mysterious group about whom many tall tales and legends have sprung up. Given their rarity and secretiveness, most people have no idea whether any of the stories are true, only that paladins are unusual fighting men, unlike any others in the world.