Solomon's Key.
Let's see: You have the ability to create and destroy blocks, which you must use to solve puzzles. These puzzles consist of a room, where you have to first get a key, and then get to a door to get to the next level.
Sounds easy? Well, there's of course also a time limit. Still doable though. But did I mention the hordes of enemies, that one-hit kill you? And the only way to defend yourself against them is to use a fireball, which you have to pick up in every level, but when you use it, it's gone? And you can only carry three of them at a time?
Well, it doesn't matter, because all the enemies respawn, yo it's not like you really gain anything by killing them.
To recap: You have to solve a puzzle in a time limit (I think it's 99 seconds, can't remember) while being chased by almost unkillable monsters, who kill you when you touch them. Of course, you only have a limited amount of continues, and if you lose all of them, it's back to the start.
Now, even if you should somehow manage to beat it, you still haven't actually beat the game. Because to get 100%, you have to find a ton of hidden stuff in the rooms, that'll take you to bonus levels.
Now the sequel Solomon's Key 2 (Fire 'n ice) is much more forgiving. It focuses entirely on the puzzle element, and there's no action or platforming. The puzzles have a nice difficulty curve, and while it starts very easy, the later levels can be real brainteasers. Except for the boss levels there are no time limits and you can retry every level as often as you want.
It also features probably the first level editor I ever saw in a game. Sadly you can't save those levels, but it's still fun messing around with it and letting friends play your creations.
Definitely an underrated gem, that sadly not even the biggest NES buffs seem to know about.