Wario land II for the game boy? Not sure if it’s exactly what you mean, but I remember playing it as a kid and being similarly delighted to discover there were multiple, non-signposted paths through the game. One in particular: at the beginning of the game, wario’s castle is under siege and you begin by pressing any button to wake him up. If you do nothing, though, wario stays asleep and after a minute or two some enemies break into his room and carry him out of the castle, still asleep. This effectively starts an alternative storyline with a bunch of new levels.
As a kid I discovered it completely by accident: I began a new game, went to the bathroom, and came back to find wario outside his castle, rather than asleep in his bed. I was like wtf but also super excited there was way more to the game than I initially thought. Also that it was a kinda dynamic world that actually responded in interesting ways to my (lack of) input.