I agree. The paladin as "guy in heavy armor with longsword who melees and smites evil" is a perfectly valid character choice. But a paladin/rogue, a halfling who scouts, disarms traps, and uses his diplomacy to avoid combat when possible but boldly stands his ground when his village is threatened, is also a perfectly valid character choice.
If you wanted to avoid having people take one level of paladin "just because", you could always just ditch the paladin class altogether and make it a series of feats.
Paladin(1): Requires LG, can only be taken at first level -- the person is chosen by their deity to be a defender of that deity's morals, a force of justice. They gain Detect Evil and the ability to Smite Evil once per day.
Paladin(2): Requires Paladin(1), 3rd level or higher -- the paladin's perserverence gives them divine protection. They gain Divine Grace (or whatever the Cha+ to saves is), as well as immunity to Fear.
Paladin(3): Requires Paladin(2) -- the paladin learns to channel his energy to positive ends. They gain Disease Immunity and the ability to Lay on Hands.
Paladin(4): Requires Paladin(3) -- the paladin is now a true disciple of his deity. They gain the ability to Remove Disease once per week for every four character levels, and may turn undead at one-half their character level (do not count cleric levels -- a cleric8/fighter4 turns undead as a 10th level cleric).
Paladin(5): Required Paladin(4) -- the paladin gains a mount.
There. It's rough, but a dedicated person, ie, one willing to put all of their normal feats up through 12th level in there, would reap the benefits regardless of whether they were a "fighter" paladin, a "cleric" paladin, a "ranger" paladin, or a "sorcerer" paladin.
-Tacky