To my mind, a "complex" fighter should...
(1) Have exploits that target saving throws
(2) Have exploits that impose conditions on targets in addition to grappled or prone
(3) Have options to choose from that are more potent as the fighter gains levels
(4) Have enough exploits that a fighter has about, say, a half-dozen options at any given time - or at any rate, enough options to feel like they have to weigh up their choices and make round-to-round decisions about what to do in a fight, but not so many that they feel overwhelmed. (Leave that for the wizards!)
(5) Have exploits be situationally useful on the whole rather than a "single best option" - so, for instance, if you're fighting a giant, you'll want to use exploits that are good against giants (ones that take advantage of their usually-poor Dexterity), and if you're fighting a lich, you'll want to use exploits that are good against liches (Mage Slayer as an "exploit" rather than a feat, say).
(6) Have these exploits grouped in thematic categories that I like to call martial disciplines and that would be about equivalent to the concept of spell schools.
(7) Have several features currently gated behind feats - Shield Master, Mage Slayer, Sentinel, that sort of thing - become exploits, more widely available.
(8) Have better access to exploits than everyone else, with some classes having better access to thematically appropriate sets of exploits.
By exploits, I mean discrete combat abilities.
A "complex" fighter should also have more out-of-combat functionality, compared to the PHB fighter. If nothing else, improved versions of Remarkable Athlete and Know Your Enemy should be core features.
One last thing about exploits: in my view, no two exploits should do exactly the same thing, although it's all right if some exploits might do very similar things if they approach them from different mechanical and narrative/thematic directions (like how a "multiattack" exploit might be different when it's "you swing your giant axe around a few times" versus "you unleash a flurry of jabs with your daggers").
I believe A5E does a pretty good job of meeting the above requirements; if I may toot my own horn, I feel pretty good about the homebrew combat exploit system I have been working on for some time in terms of doing the same.
Edit to add: I should like to add that in my view, the goal is to make the mechanics of the fighter match the theme of being a master of arms. The fighter should be able to do stuff with weapons that other martials either just can't do, or can't do to the same extent, where the PHB fighter (with the exception of the Battlemaster, which I would consider a starting point for the above) mostly just does the same thing with weapons as other martials do (i.e., weapon attacks against AC for damage), just more often - indeed, since most games end before 10th level, one hardly ever sees the fighter even get to do that much, the odd action surge notwithstanding.