One of the things that made the 4E fighter stand out for me was that weapon choice actually mattered because of the feats and powers associated with each weapon type. Axes were less accurate but got bigger crits, spears and polearms were better for tripping and forced movement, swords were more accurate and better for attacks of opportunity (and therefore controlling your opponents' movement), hammers could daze and stun, etc. For a complex fighter, your choice of weapon should have as much an effect on your character's play style as a wizard's choice of spells does.
(Throwing out different ideas separately for discussion.)
My complex fighter has Stances. Only one can be active at a time, and while active they grant an ongoing bonus. Starting and being in a stance generally is noticable. They can add to AC, negate disadvantage, give a bonus to thrown weapons, etc. Stances require Concentration, and a bonus action to start if in combat.
There are ones for forced marches, recovering exhaustion if kept for 1 hour, feats of athletics, and the like. There's also ones like "Ready!" which is not noticeable when assuming/in, but gives a bonus to Initiative, or "Fade to background" which grants stealth-like getting overlooked if you are appropriate to the scene. (Dressed like a guard in the palace, hanging in a tavern, etc.)
1) class abilities that address the social and exploration pillars. So probably translates into more complexity at the character build level since you shouldn't be able to be good at everything and I'd want a menu of options rather than every fighter being forced into 'good looking leader of men' option say
2) interesting choices for the player to make in game. So stances, more powerful not always available abilities, some kind of currency you probably have to juggle like focus points, etc.
3) related to 2 but more ways to effect a encounter than HP attrition. Being able to trade HP attrition for some control or other effect adds complexity
4) mythic martial type abilities at higher level -- maybe don't have to be more complex but I think probably do add something different like more narrative abilities which could be a type of complexity
4e martials, Bo9s, and A5e are all good places to look for inspiration but I think there could be something even better.
I mentioned that i had some stances I'd made up, but I actually quite like the way they've done stances in the rokugan adventures book so I might add those to the fighter, or at least mine them for ideas.
I know this is meant to be just about fighters, but another thing I want to test is warcries and rage abilities for the barbarian. I set them up so that the barbarian can do different things when activating or during a rage. Things like move and attack as part of activating the rage or unleashing a thunderous shout that damages and pushes back the enemy.