Grimsby the Fantastic Wizard's page

I think it's a great addition to Human versatility.

d20 3.5 Humans get a Bonus Feat and a Bonus Skill Point each level.

Pathfinder Alpha Humans still get the Bonus Feat.
They get to pick an extra skill to be trained in, regardless of if it is on their class list, and it is always considered a class skill.
They get a free weapon proficiency of your choice, which is like another free feat (this can be things like Exotic Weapon Proficiency Spiked Chain / Bastard Sword / Courtblade / Repeating Crossbow, etc.)
They get a +2 Bonus to any Attribute of your choice.
Oh, and Favored Class: Any actually matters now because it's a possible +20 hp.

That is powerful and definitely attractive and yet, it allows for a very, very wide range of customization - which is the point. Human subtypes are not neccessary when the base race is so versatile and customizable.

Actually having a flat bonus with stacks with Power Attack and Divine Might is a good thing for the power level of the class, since those things factor into critical multipliers - a smart Paladin uses a weapon that crits often (falchion, courtblade) or crits very hard (scythe) and takes Improved Critical or gets their weapon the Keen property.

Also, the Paladin is not limited to one smite per round, and the Extra Smite feat from Complete Warrior helps a lot.

In any event your average L20 Paladin with a Belt of Giant's Strength +6 and a Cloak of Charisma (Nymph's Cloak, harumph!) is a Balor shredder, and not something I consider underpowered at all.

However, they are kind of a one trick pony and if the foe ain't evil, that's a bit of a problem. Of course, if the foe isn't evil, that's where diplomacy comes in.

a) Detect Evil at will is not a problem when Undetectable Alignment exists. It is primarily a supernatural sense that allows you to determine if a threat is in the immediate area or behind that next door in the dungeon. It's not going to catch the Assassin sneaking into your bedroom or foil the BBEG of the campaign unless the DM is terrifically stupid. Anyone with UMD and the ability to buy a wand or who can hire a 2nd level Bard henchman can be immune to the effect all day, every day.

The skeletons and zombies over there aren't going to bother with such things though, and neither are the unrepentant ravaging evils that don't care if they get found out (your average Balor, Blackguard, etc).

If using a spell like that to balance another spell feels contrived to you, I don't know what to tell you - there are plenty of examples of spell / counterspell couplings: Shield and Magic Missile; Scry and Scry Trap, etc.

b) I concur that there are a lot of empty levels, even if Smite Evil and Lay on Hands and your mount are all steadily improving.

I would suggest pushing the class the direction of the Cavalier / Knight, with things like bonus feats for mounted combat and the ability to take damage for allies, whether magical (Shield Other?) or more conventional (Warder, Bodyguard, Knight, Knight Protector, etc).

c) Alternatively, we already have the Aura of Courage, so other such auras and "leadership bonus" notions are desirable.