Look at mythological heroes such as Heracles or Thor. If Heracles needed to clean out a massive stable in a day, he just used his ludicrous strength to redirect a river. If Thor had business with the Midgard Serpent, he just whipped out his fishing pole. If Thor wanted to lower sea levels, he just started drinking (though this one wasn't intentional on his part). One of the best examples of Deus Ex Machina through brute superhuman strength comes from the Ramayana, where Hanuman jumps from Sri Lanka to the Himaleyas to find a mountain where healing herbs grow, then uproots the entire mountain and carries it back to Sri Lanka in a single leap...There is a strange idea that even Epic level Fighters who can go toe-to-toe with Balors and Elder Dragons should fundamentally resemble mundane humans.
Well, it is worth noting that Heracles, Thor, and Hanuman are all gods.
I'm not at all opposed to the idea of high level fighters doing superhuman things, but don't think you need to draw the lines so far out as Thor and Hanuman. At 20th level, not that my campaign ever goes there, your average (average?) fighter under my rules would probably be able to out run a horse, leap over a small building, climb a wall of ice, leap from a 200' precipice and survive the fall, and smash a stone (or a wall of force) with his bare hands. He can inspire a small army to fight with a fearless passion. His hands may well be lethal magic weapons. He can quite possibly win a bare knuckle brawl with a 3 ton giant, and drink an ogre under the table and that isn't even to begin to discuss the powers of the heirlooms and artifacts in his possession. He's no longer merely mundane; he's a superhero. That's the expectation.
None of that would give him narrative power necessarily. I'm inclined to see 'narrative power' as something of a red herring here.
I have never known in any of the games in any edition I've played a man-at-arms of any sort to be a weak class. I recognize that a very large part of that is the way I run games, but by far the most dominating character I ever encountered at any table was a fighter in a game I wasn't running. I have never seen the actual in game stats (pre-publication) for any of Gygax's wizard characters, but I have seen them for.. a fighter. As a person who has played 1e, the fighter didn't strike me as a particularly weak and scoffable character lacking 'narrative authority' or whatever you want to call it.
As for the Wizard, you don't have a lot of narrative control when you are dead. Any wizard that thinks he can get by in the greatest of dangers without a stalwarth company is soon going to rue it. The situation I strive for is this; the guy playing the wizard at the table knows he's dead meat without the brave assistance the fighter and the guy playing the fighter knows that he won't get very far at all without the brave assistance of the wizard.
Do I think that the 3e rules - or indeed the rules for any edition - have completely and fully realized this goal? No, I don't. And I fully agree that 3rd edition had this problem in spades and I don't doubt that many a new DM running his game by the RAW threw his hands up in frustration, or that many a player in such game rued the day he choose to play a lowly fighter. Back in 2nd edition, you might have said much the same thing about playing a thief. But I find that the situation is not as dire as all that.