How about changing the Leadership thing around a bit (while still eliminating it as a feat), and tie it to Fighter class levels? Maybe grant followers as per the feat, and grant weaker cohorts with levels depending on their class.
E.g., you can hire another Fighter, or a Monk, or a Barbarian, or a Rogue, or a Ranger at level-2, a Bard or a Duskblade or a Swordsage etc. at level -3, a Sorcerer or Favored Soul at level -4, or a Wizard or Cleric at level -5. You'd also need a way of incorporating NPC building rules, and have the DM build the cohort(s). That way, the Fighter class would actually be about commanding their loyal sidekick and other guys to do their bidding, AND being (slightly) kickass in one or two chosen fighting styles themselves.
Change skillpoints to 4+Int while you're at it, include Diplomacy, Spot, Listen, and Knowledge (nobility and Royalty) among their class skills, give them a good Will save, and throw in some Inspire Courage for good measure (maybe more class features to make followers more useful, even), and you're looking at one of the more interesting ways to fix the Fighter.