Why is the Paladin a problem. You mean, besides the minimum scores of Int 9, Con 9, Str 12, Wis 13 and Cha 17? Try rolling that with best 3 out of 4d6. You be there for a nice long time. So as kids, we cheated. Still, that's not the big problem. The big problem? Detect Evil.
Detect evil at up to 60' distance, as often as desired, but only when the Paladin in concentrating on the presence of evil and seeking to detect it in the right general direction.What is he, Green Lantern? "No evil shall escape my sight"
Think about it. You'll (as a DM) never be able to infiltrate the party with an evil NPC. Every character, every creature he encounters, he can just plop his detection power on and and weed out the evil. He's more effective than a black light at a crime scene.
At least with Detect Magic, it's a spell that has to be memorized. It eats up a spell slot. It has limited uses - it's not at will.
Detect Invisibility, Detect Illusion, even Detect Lie - all take a spell slot, all have fairly limited uses (but work really well when they are on target).
Why the hell did Paladins get this as an at will power? The issues to game balance are huge. Not that I thought about that was as a kid, but today I'd be Detecting Evil behind every door, before I make any turn in a corridor, before I gave the stable big my horse.
I'll rant about the continuing emanation of a Protection From Evil in a 1" radius around the Paladin later (is that 1" as in an inch, or 1" as in AD&D 10'?).
All this and a cold from hell. I could have used that Protection From Evil shit, or the immunity to disease. Sigh.