The only change I propose to fighters ever since 3.0 came out was that they should have more starting skills. I understand that it represents the fighters devotion to feats and martial proficiencies as explained with the cleric, paladin, and wizard. I think if fighters had 4 starting points (like for some reason the barbarian)I would see no problems in fighters, at all. And god forbid a fighter can have Acrobatics and Perception as class skills, you know every martial class in should have....
It could be me, I see skills as more flavor for characters and group balancing rather than the 3 main forces of the game, skills, combat, and magic.