For a Gameboy suggestion, Super Mario Land 2: 6 Golden Coins. This is the first game featuring Wario. You can complete the worlds in any order. When you get a game over you lose all the Golden Coins you've obtained which act.as keys to enter the final world. So you still have to reheat the final stage in each world again if you get a game over. One of the worlds is a giant mechanical Mario you get to go through!
I haven't played this, but the next game in the "series" is Wario Land: Super Mario Land 3 lmao. But I have played Wario Land II. Wario Land II is interesting because you cannot die in the game. Getting hit makes you lose a few coins and that's it. When a boss hits you you get sent back in the stage a bit. Rather than having power ups, some of the enemies affect you. For example, if a bee stings you then you begin to swell up and float. If you're lit on fire then you catch on fire and can burn certain blocks. These are fun because they're oftentimes the only way to progress.
A lot of Gameboy games were kinda crappy. No offense to them or if you liked them, but these two still really hold up. They look and sound amazing. It's a shame to me that so many people seem to remember and are nostalgic for the first Super Mario Land but haven't played the second which is WAY better.