Returning the Fighter to relevance.

[Milo v3]

The hardest non scaling things on that list would be:
Capable of fighting while scaling a smooth canyon cliff face* (feels 9th ish)
Lead Troops (feels 6th ish)
Be GOOD at politics (feels 9th ish)
*Climb a cliff was ambiguous and different levels would have different difficulties expected.

So I would guess 9th level as a good rough estimate of a place to try it from. I would also recommend a 1st and 5th level snapshots since many of those accomplishments feel like they are either 1st or low level.

I'll do 1/5/10 rather than 1/5/9 just for numerical rhythem.

No one enjoys having toys taken away, but nerfing a wizard to make fighter relevant can be effective. Consider this:

This would dramatically alter the game in favor of fighters because a high level fighter, with his magical equipment and feat repertoire, becomes a relatively good buffing platform. Spellcasters could no longer be effective as fighters, since self-buffing strategies waste most spells and have high uncertainty in effect. Furthermore, although spellcasters can be magically healed, it is a more difficult process. In partial compensation, spellcasters at least resist enemy spells well. A spellcaster summoning monsters remains a powerful strategy, but since only non-SLA monsters can be easily buffed, summoned monsters generally cannot fight better than an appropriately leveled and outfitted fighter. Spellcasters have less ability to affect monsters at higher levels, because all of the SLA using ones have a high spell resistance. Mailman-style strategies at least remain effective with SR:No spells.

The above pushes towards a much more cooperative form of play where every party needs both spell sources and spell sinks to be fully effective. Obviously, it makes challenges more difficult, but not so difficult that level appropriate parties cannot deal with it.

That makes "Personal" spells useless. My preferred change to wizard is to stop their spell list at 6th level (they still have spell slots above 6 though), since it weakens wizards when they are at their strongest while not nerfing them in the parts of the game where they are "fine".

Also, you seem to mistake being a Fighter for being a general of an army. That is not the case, and should not be the case with the base class of Fighter. What you describe is much more Marshal than Fighter, because Marshals are built to be leading military groups. Fighters should trade off astronomical combat power when they are hitting for the non-personal fighting power. Being a warrior needs far, far fewer of those than half. A warrior is not necessarily a trained soldier or anything like a general. They can just be amazing at Fighting alone, no backup, no politics, just fighting on their own with little to no ability at anything else.

According to PHP and PF's core rule book, being an overlord or someone who rouses the hearts of armies are perfectly valid fighter concepts. Fighters are allowed to be more than just "Durrrr I can stab things".