Interesting! 1) and 2) has not come up for us in our games. 2) I think has been aided by use of Challenges and Contests and Tests and all the like, plus ensuring scene setup is different and diverse (and often including a Scene Distinction). 1) might be influenced by what prime sets are chosen and perhaps how the players engage/flow with both the mechanics and the narrative (including the direction/order of each).
3) I've been concerned about, but fortunately it too has yet to rear its head too much. (Or maybe I've been good/lucky at adjusting along the way to keep things from fully slipping into the death spiral.)
4) is an interesting one. I'd say leaning heavily into SFX (and/or Abilities) as a progression tool/item might be the way to go, as that adds more unique/varied options beyond raising a die-based prime set. (Though those are certainly important to allow to be bumped as well.)
Good points, and my experiences generally follow yours.
For 1. you can (a) lean hard on "the outcome of a roll should (drastically) change the situation" which narratively suggests that doing the same thing over again isn't really logical, and (b) traits that suggest -- or even mechanically require -- needing to vary your approach. Values, Relationships, and Affiliations are perhaps a bit more "obvious" for that (meaning option b) than Attributes might be, and Approaches (from Fate) are an even more heavy-handed way to do that. Aside from simple trait choices, though, are things like Shaken and Stricken being tied to an Attribute (or other trait set), and therefore if a player chooses to use the Attribute that's Shaken then their opponent gets to add a die to their pool, forcing them to consider wisely whether or not to use that trait. I've had a few hacks using Approaches where you actually take Stress against an Approach and shut it down once the Stress is higher than the Approach's rating. For example, Spidey has Stealthy d8 but has d10 Stress on it, so he can't use Stealthy, and has to instead rely on Cunning or Forceful.
For 3. I also can't say I've experienced that but notably I use Stress in every Cortex game I've played, and tend to rely on that enough that even when Complications are in play, there are rarely too many of them applied on any given character, such that their opponents are gaining loads of extra dice against them. (Remember, when Stress is in play, you only add a single appropriate Stress die, as opposed to Complications where you add any + all Complications that apply. If you have both Stress and Complications in play, this could lead to both being appropriate, and thus many appropriate Complications piling up, but like I said, I don't often find this to be the case.)
For 4. I have a strong opinion: I don't see Cortex as a game of mechanical advancement. Yes, there can be some and I certainly don't disallow it or anything, but having come from primarily Marvel Heroic, I see advancement more as either very, very minor changes to a character's datafile (a new SFX, a new Specialty, swapping a few existing ratings within a given Trait set), or a radical change that is best performed by simply building a (mostly or completely) new datafile. The only semi-consistent changes come from closing out and choosing a new Milestone. In my mind, the text in the Cortex Prime Game Handbook about "Session-Focused" play says it best: the game is meant to have a clear character arc for each Player Character in a given session, as opposed to happening over a larger span of time like an adventure (3-5 sessions) or a campaign (5+ sessions). While I've done long campaigns, some PCs changed very little mechanically, but their "story arc" might have seem them make huge decisions that changed the nature of their character's viewpoints or allegiances.
Admittedly, that is a strong preference and a specific reading of the game that I think is not fundamental to how the game works. That said, the game's mechanics do require some deep thoughts about advancement before you can make it work well on more "involved" level with the mechanics of a given Player Character. SFX that need to be "unlocked" and spending XP for unlockable story-specific upgrades (as seen in Marvel) are two ways of adding a lot of oomph there, if you want it.
