Progression doesn't have to be power. Can be social, financial, score-ranking, military hierarchy, it can be the amount of the world explored and landmarks visited, it can be progression through huge arching questlines, it can be progression to increasingly cooler looking appearances that "testify" to your skill to other players, it can be access to exclusive gathering halls / drinking holes in the cities. It can sometimes even just be a pat-on-the-back gold-sticker, or a increasingly filled up collection of stamps/achievements, or some level of tiered titling ("Silver member", "Gold member"). Many players ignore the non-gameplay ones though.
More importantly, progression can also include new abilities, even combat abilities, as long as it doesn't give an extreme edge. You can look to the more modern Call of Duty games for design inspiration here (don't dismiss their design values out of hand for not being the same genre of game) - In Modern Warfare / BlackOps / Advanced Warfare, players "level up", unlock and choose to equip a large number of different equipment and attachments. Despite this, players with higher equipment don't have an advantage over players with lower level equipment. The different equipment is "unlocked" giving forms of progression, and chosen to be equipped and chosen what accessories giving forms of player customization. It is very incredibly impressively balanced. Everyone thinks their equipment setup (their "loadout") is the best, but everyone has a different loadout, creating a wide variety of different possibilities - and a wide variety of different challenges to overcome from your opponents.
While occasionally, players complain that WeaponX is overpowered ("Ugh noobtubers!"), but if this was actually true, alot more people would naturally use the more powerful loadouts. Instead, we see huge differences in loadouts. And even if one weapon is slightly unbalanced (hard to measure), out of 30 weapons and >500 variations, it's still a very impressive design feat.
Unlocked upgrades don't have to be better, they can just be different, and provide different styles of gameplay, without creating disadvantages in power. Infact, one might argue that the default WeaponB is 1 point of damage higher than WeaponA is actually the bare-bones lazy way to design equipment.
Players need to be challenged. Getting more powerful actually decreases challenge. Players need to unlock gameplay possibilities, not power.
At first, too many choices can be overwhelming. So you have to provide fewer choices to players early on, and introduce more choices gradually. This works hand-in-hand with progression - unlock new ways to play the game, unlock new tools that enable new tactics. Unlock new ways to overcome challenges, don't unlock power that makes the challenges less of a challenge.
You can also look to League of Legends (again, don't be dismissive because it's not the same genre). League of Legends currently has 123 different champions. While they do a slightly poorer job at keeping them balanced, they are still amazingly close in balance (and the imbalances only really are revealed at more skilled levels of play). The champions have different play styles coming from their different stats and abilities creating different ways to overcome challenges (and posing different challenges for players who are facing them).
While the champions have alot of overlap and similarities (it'd be hard not to, with over 100 different playable characters), overall there is alot of variation. Most fall into several different styles of play (or roles to fill), but even those styles have subtle variations within them. And players don't have to stick to the standard play styles anyway - but the champions' abilities enable different styles of play, different choices and open up different opportunities when the right circumstances come along.
Or take Halo for example. I haven't played any Halo game in years, but think back to Halo 1. You have a rocket launcher, a pistol, a battle rifle, a sniper rifle, shotgun, a few alien weapons, grenades (normal and sticky), etc...
Each weapon isn't necessarily more powerful than the others, though some were unbalanced at higher levels of play (like the pistol in Halo 1), they vary in strengths but their strengths are only fully beneficial in the right circumstances. Your (changeable) weapon compliments your (changing) environment to face changing enemies (other players, also with changing weapons) to create dynamic, interesting, and enjoyable challenges and experiences.
While both Halo and Modern Warfare are examples of weapons, I'm not trying to suggest you give players weapons. The exact same concept can be applied to skills/magic/abilities and even other gameplay mechanics. Unlock options, not power. Introduce new choices, don't decrease challenge.
Think about "Doom" for a second. Each gun you get varies mostly just by power. Mostly, the only reason why you'd use "weaker" guns is to conserve ammo for your "good" weapons. That's not how you want progression to work.
You ever play the original Thief, or Deus Ex? Those games weren't without gameplay ruining flaws either (Dragon Tooth sword anyone?), but what did they right were give tools to provide choices in how to approach challenges. Thief had: water arrows, noisemaker arrows, rope arrows, moss arrows, mines, as a very clear illustration.
Deus Ex had the "tools" hidden as abilities and weapons: depending how you progress your character, different ways of interacting with the environment (and with enemies) would become unlocked through your abilities, opening up more choices for the player to consider when overcoming the obstacles the game throws at them.
Just to be clear: I'm not talking about mechanics, genres, how your combat works or how you should make your gameplay. I'm talking about the common concept behind the examples above: They empower and unlock player choices, not merely boosting player stats.
