Well, 4e did it, so hard, maybe but not impossible.
4e got around a lot of the problems by declaring that when fluff and crunch conflicted, crunch won, regardless of how conceptually silly the result might be. I really don't think that 5e will keep that decision. I certainly hope it doesn't.
You're not describing hard to design, you're describing a prejudice against not merely a complex fighter, but a capable fighter. You are, indeed, describing an opinion - held by "many groups" - that the fighter must suck.
I have a hard time seeing how it is possible that a fighter that can kill a dragon in single combat sucks, UNLESS he can also grapple the foe, whose foot weighs more than the fighter's entire encumbrance allotment.
It is not designing a complex, balanced fighter that is the difficulty. It is overcoming the prejudice against a fighter that has mere parity with casters that is hard.
There is no balance to be obtained by making one class tightly limited by spurious 'realism,' and others completely unrestrained in breadth and scope of power. It doesn't matter if you have the fighter hitting and one-shotting every monster in the book - he'll just be an overpowered choiceless beatstick instead of an underpowered choiceless beatstick.
So your problem has absolutely nothing to do with Simple Fighter vs. Complex Fighter, and everything to do with Why Fighter At All?
Actually, that is an easy question to answer. Seriously. Really, really, really easy. What do wizards fear? Huge hit-point, high offense enemies that shed magic like water off a duck's back. That is what a high level Fighters needs to be. That is what high level monsters need to be. All of a sudden, Fighters do the fighting, while the wizards provide backup. Complex vs Simple doesn't even enter the equation, although some attention to out-of-combat abilities would be nice. 3e's 2 skillpoints/level with a weak skill list was, well, indefensible.
Seriously, I'm sorry if you didn't mean this way and I've just picked your thread to throw down this particular gauntlet, but it's an unacceptable demand. If 5e is going to be an 'inclusive' edition, it's going to have to include a balanced fighter that has parity with casters. It can be ignored by anyone who doesn't like it, but it needs to be provided. Not just the fighter, but each martial or 'non-caster' class, Warlord and Rogue as well, and Ranger if there's a non-casting version of it.
Yup. Caster/non-Caster parity. Quite easily obtained. Just hand out magic resistance like candy. Kinda like 1e, where all the big names (and little names) saved on 2s. Scarily often, with Magic Resistance percentages on top. It is *amazing* how much ground Fighters lost when they went from saving on 2s and killing wizards in 1.5 rounds (1e/2e) to saving on 15s and taking 3-4 rounds to drop a (decently built) wizard (3e).
Again though, I have no idea how the Simple/Complex dichotomy applies.