I almost feel like the solution is not to give Fighters exclusive access to leadership, but rather to make the Fighter a "pet" that you can pick up as a member of another class, possibly by means of a feat, but perhaps more with a class feature.
6th Level Rogue Feature - "Kneebreaker" You gain a thuggish companion who acts as your muscle when brute force is needed over finesse. He remains one level below you.
6th Level Paladin Feature - "Squire" You gain a trustworthy stalwart who, while good hearted, didn't have what it took to be a real Warrior of God. That won't stop him from trying to help fight the forces of darkness.
6th Level Monk Feature - "Chris Tucker/Owen Wilson" You get an obnoxious sidekick who fights with real weapons, yet somehow remains less relevant than you at all times, probably because he's just so damn annoying.