Turn Undead (see CD, for one reasonable variant).
The Monk (chuck it in OA, with more style and options, and scrap it from core). Have an unarmed combat feat chain, or more than one - whatever. Fighters should rock in this area if they pour some of their many feats into it. More than anyone else in core. They're Fighters: they fight.
Paladin should be a prestige class, as per Blackguard (kinda). It's not something you "just do" as a very low level advanturer. Not IMO, anyway. Also, they shouldn't be limited to LG. That's just sanctified beef animal. At least go for the 4 extremes, as per UA. It was already a holy (or unholy, etc.) fighter/cleric anyway - why not make it official.
Same goes for the Ranger (the D&D-type Ranger, that is). Prestige class, thanks. In this case, already a fighter/druid anyway. . .
Bard, too. And here we have the rogue/sorcerer, or fighter/rogue/sorcerer. . .
See UA for some basic ideas, if not great implementations, for all the above PrC versions of those core base classes.
I agree that the unarmed vs. natural attacks thing is a mess, too.