Again, 100% agree with these points. I've added a few options to address some of these in limited fashion, although I'm not sure if I've gone far enough. For example, Heroic Resilience allows a character the chance to make a second saving throw against an ongoing magical effect in the following round. Is it enough? I haven't seen it in play yet, and I'm leery of tilting too far in one direction. Close quarters fighting (AoO against all grapple attempts) should help characters avoid the peril of the many creatures with Improved Grab, but again, I don't know if that goes far enough.
Close Quarters Fighting is an example of something that fighters absolutely need to stay relevant, but it brings up an important point here and that is feat tax. If you can compose a list of feats a fighter absolutely has to have to stay relevant, then you are actually creating a count of how many feat slots the fighter is short of in its design to being balanced. You have to either grant these feats as class abilities or else add that many slots to the fighter if you are going to go this route. My rebuilt fighter gets 17 bonus feats and six class abilities compared to the 11 bonus feats of the stock fighter, filling in for what I feel is a short fall of 12
feats.
I like the idea to make skills more generally useful, so that's something I'll think about. It would go a long way toward providing non-spellcasting classes more out of combat flexibility.
The rebuilt fighter also gets 4 skill points and access to four new skills: leadership, tactics, porter, and run. The first two let you do minor buffs in combat and remove morale debuffs, plus open up feat trees to make you good at that stuff (like using them as free actions). The second two grant you flat bonus to your carrying capacity and base movement rate, both of which give you problem solving ability. In the long run I also intend to tie tactics and leadership to a mass combat system, so that fighters naturally excel other classes in leading armies in battle.
I don't really have a fix for this right now, but I'm not convinced it's the most important thing to solve right away.
It's more important than you think. If you have a 1e background, you'll note that spellcaster's didn't outshine fighters at least (thieves were another matter) so completely in earlier versions of the game. One of the reasons was the math of hit points. In early editions, fighters (and fighter sub-classes) had about twice as many hit points as other classes - 5.5 per level versus 2.5 per level. Bonus hit points from CON were fairly rare, but if they did exist fighters got a hidden class feature of getting roughly twice as much advantage out of high CON as other classes. Fighter with 18 CON could get +4 bonus hit points, but all non-fighter classes were capped at a maximum bonus of +2. The result was that fighters were very durable. But in 3.X, CON bonuses are quite common and further commonly buffed. If a Wizard and a Fighter both have effectively 20 CON, then the relative durability of the Wizard has gone way up - 10.5 per level versus 7.5 per level is a much smaller relative gap. In essence, spellcasters were made much less squishy while martial classes were given no compensating bonus. Further, this just feeds into the fact that spellcasters are self-reliant and martial classes are not, because divine spellcasters can repair their wounds, effectively tanking better than the martial classes.
Two numbers that are very important in this discussion are base Fortitude save bonus and base attack bonus. What you want to do is introduce feats that both require good base numbers in these categories but also scale with those numbers. As a small hint, the way the Toughness feat works in my game is it grants you your base Fortitude save bonus + 3 bonus hit points. Thus, a wizard that takes the feat at first level gets +3 hit points, but a fighter gets +5. Further, at 20th level, the feat now grants the 20th level fighter +15 hit points. And the feat Great Fortitude increases your base Fortitude save bonus directly, so as a small side effect, if you have both feats you also gain +2 hit points.
This, on the other hand, is huge. As I mentioned above, I have a few options I'm working with right now, but I'll need some in-game feedback before determining if it does enough.
Imagine for example a feat that says, "If you suffer a condition like dazzled, stunned, dazed, blah blah blah, that condition automatically lasts 1 round less". If that doesn't go far enough, you could just flat out half the duration of the conditions (rounding down).
Yes! I don't want want to focus just on damage, and as the OP says, I'm really looking for additional tactical options. A wizard's ability to, say, cast a Wall of Stone and completely divide the battlefield is pretty powerful.
It's one of those nigh game breaking abilities to change the rules of reality. You are going to have a hard time matching that and not turning a martial character into a spell-caster. It's not just the ability it grants in combat, but the fact that it is a massively powerful problem solver for a wide variety of out of combat situations.
You keep focusing on dealing damage in combat as if that's the real problem martials face. It's not. The real problem is what does a martial do in response to a wall of stone or more to the point a wall of force being raised in their face. And that points to general problems that extend outside the area of the martial class design, like the fact that wall of force is written to have no responses to it other than equally powerful magic. It's written in absolute language and without any sort of quantification. It would be one thing if it said, "The wall of force has hardness 100." Instead, it has immunity. If you want martials to compete with spellcasters, one area you have to start dealing with is the fact that spellcasters get agency without qualification or quantification.
As for overcoming environmental hazards, that's one area I haven't given much thought to. It seems that skills could help here (jump, climb, balance, escape artist, etc).
Survival, heal, endurance. The Endurance feat can be very powerful if you have a hazards system well tied to it, and I've even considered turning Endurance into a skill. You have to start making skills matter in very tangible ways, and if that means things like allowing the Heal skill to heal wounds via first aid in some limited way, then you need to go there. Of course, skills don't always just help martials, but if you start looking at martials get more skills than spellcasters and the fact that spell-casting itself is a skill sink (concentration, spellcraft and in my game scry) then you can start getting more balance going.
I don't know if I said it explicitly, but I'm not interested in nerfing spell-casters, so the solution is that the non-casters need some more options.
I don't know what you mean by nerf, but you have to be very careful about increasing the available spells or you will never get balance. And you have to really pay close attention to how spells work. Spells like Spider Climb and Jump in and of themselves go a long way to making Martials second class citizens because they let you do things as a low level character or with a trivial exercise of power that martials would struggle to do as a high level character.