[Baines]

Megaman is a good example of increasing abilities making a relatively free-path game easier as you progress.

There is a possible solution. The funny thing is that Megaman X arguably did the opposite

In Megaman X, beating certain stages affected other stages. Except there it almost always made the other stages easier. Fire is replaced with safe ice. A pit floods with water, making an otherwise impossible jump possible. Etc.

Instead, you could make aspects of the game harder as the player upgrades.

For example, if the player gets a homing shot weapon, upgrade a docile straight flying drone enemy into something more aggressive. When the player gets the ability to swim freely underwater, flood a few areas and put more dangerous enemies there.

You don't have to make everything more difficult. But change a few things so that the difficulty at least keeps pace.

With a lot of power-ups and a large area, you still need to be careful though. You don't necessarily want to shut out an area with too high a difficulty if a player gets a really weird power-up combination. Or maybe you might not mind... Keeping changes related to the powerups could help in that regard. You don't necessarily want pure evil in the skies to appear from someone grabbing a swim boost. (Or maybe you do, if you've got enough underwater alternate routes.)

Maybe a player might not even notice a change, if he takes items in a particular order. Maybe he won't grab the item that triggers earthquakes (reshaping) primarily in the lightning gun and multi-shot areas until after he has both those weapons. Don't worry. Maybe that just was his good luck. (Or possibly bad, if it did make a spot or two easier.) You don't necessarily want the player dreading picking up powerups, though having a knowing player actually pause to consider might be good.