How would you implement difficulty in a non-linear game. A good game should get more challenging as it you progress ,but if you can choose what to do in what order you have to make them all equally challenging .This means the game becomes easier as it progresses.
I indirectly answered this already with my metroidvania solution, having areas you’ve beaten get easier, and just straight up tuning all the other areas around a base power level, but you do bring up a point that I didn’t consider: You want endgame areas to be harder, whether by levels or just tuning, but you don’t want players ending up there early on by accident.
When people speedrun Quake, they do it in reverse order actually, because you’re allowed to pick whatever episode you want. So people choose episode 4 first. I think they mix up 2 and 3 because of some routing detail that makes it faster, but I can’t imagine why.
The obvious thing you can do is follow from the metroidvania solution and make the other unbeaten areas harder after you beat one. Actually, if you did it on a level beyond just number buffs, like world tendency in demon’s souls, by changing enemy and level arrangements, then it might add to the replayability of the game, beating the levels in different orders to see their beefed up forms.
The other, probably more obvious, thing you can do is organize the levels so people have to go through the easier ones to get to the harder ones.
Or alternatively, you could not really worry about it. The intention of the warp pipes in the original Super Mario Bros was apparently so if players felt the early areas were too easy, they could skip to the harder ones. It’s one of the things I like about dark souls, going directly to blight town to fight Quelaag, or into the catacombs to grab the gravelord sword/rite of kindling.
The larger issue is making it so unskilled players don’t go to areas out of their league by accident, like accidentally going into the graveyard from firelink. The best way to do that perhaps is to make it so sequence breaking involves low affordance and/or difficult to perform tricks. Like in order to get to blighttown first, you need to either kill ingward so you can get the key to the seal and open the seal, which you won’t know how to do until the late game, or pick the master key and open the door at the entrance of new londo, which you would be hard pressed to find just starting out.
The graveyard at firelink is a good example of how not to do this. A lot of people go that way by accident because it’s really high affordance, you’re practically lead that way. I fought down to the first bonfire in the catacombs on my first time playing the game, not realizing it wasn’t the way I was supposed to go. And that was patch 1.0! The skeletons didn’t even drop souls back then! If the way into the graveyard was obscured somehow to dissuade beginners, then it would probably contribute to a better experience for them, while still allowing advanced players to do as they please.