For one, I think you'd have to focus on alternative playstyles beyond "shoot X for Y amount of times" like with Tartarus and Sesa' Refumee. Metroid Prime does a pretty good job with boss fights, Echoes especially. As far as in-universe stuff, I think CE's "frog blast the vent core" segment and Halo 3's Scarabs were good examples of boss battles in the Halo sandbox. Fighting infantry-sized enemies should probably be reduced to minibosses with really good AI, for example Elite Ultras in Halo Reach. There's more potential for bosses that are player versus environment that give you a lot more freedom in combat, like the aforementioned Maw ventcore gauntlet. Of course you'll have to unload some rounds into bosses, but the Maw fight was really more about map traversal, efficient movement and proper aim, just like CE's design philosophy. While you don't ever really need it, there's also the risk and reward of the Armory where you can get more ammo to damage the vent cores, but at the cost of having to slog through Flood to get back there.
The first Enforcer fight was also handled pretty well, imo. You're given substantial ammo (including a hidden Carbine loaded way beyond max capacity) and several routes under the gondola to approach it from multiple sides. It also manages to stick to a known combat design philosiphy in that you can take down its shields to damage it head-on, or flank it to get it by surprise. It can also be hampered in a variety of ways such as picking off its arms, forerunner-needler projectors, etc. Or, it can be skipped entirely! By avoiding its projectiles and hitting all four conduits and then activating the gondola, it'll explode. The first Enforcer fight is pretty much the exception to prove the rule in terms of bad boss fights in Halo 2. It can evidently be done, and done so well that multiple playstyles can take it on - marksmen can take down its shields and disable its weapons one by one, grenadiers can flank it and blow it up from multiple angles, and speedrunners can forego it altogether - it's just a matter of designing enemies that can provide that experience.
I think part of the issue is the inherent power creep / serial escalation introduced in the newer titles. An Enforcer is a run-of-the-mill, albeit advanced, Forerunner sentry. Obviously this design philosophy would be harder to implement against a historically unkillable entity like a one-on-one Didact fight. I feel like automatons or more personal engagements are generally the way to go, and I've always really wanted a Strato-Sentinel fight. I feel like Strato-Sentinels would be a natural extension of something like the Enforcer fight with a little Scarab thrown in.
Once you damage the Strato-Sentinel enough you could even hop in and pilot it like a mech!
