I was thinking about creating a thread about this, but I figure this is the right place to mention it.
When Casey described the reasons he liked the original LoZ on NES, one game immediately came to my mind: King's Field.
It's actually not tilebased neither 2D, but I feel it perfectly masters the aspects Casey mentioned, like little to no handholding, no constraints where you can go in the world, etc.
I highly recommend anyone looking for those kinds of features to at least experiment with it. It's the very first actual 3D free roaming first person game on the original Playstation I think. The graphics and framerate are quite bad for today's standards, but in my opinion the core gameplay and concepts actually hold quite well.
I'd just like to mention here that the King's Field series is actually the precurssor to the much more famous Demon's / Dark Souls games. I have Demon's Souls but I've not started playing it yet, but from what I hear, some of those core aspects are preserved as well.
TLDR: play King's Field on the PSX for some very open and old school, no handholding design.
Whenever I hear you talking about block puzzles, Goof Troop from the SNES immediately come to mind. If you guys have not played it already, I highly recommend it (for completely different reasons that I recommended King's Field too).
It's a tile based, 2D, heavily puzzle based action game in the universe of Disney's Gooffy and Max characters, where you can use items to traverse the evirnoment. I think it was Shinji Mikami's very first game (you may know him from the Resident Evil series, or more recently, from The Evil Within).
It's a very short and somewhat easy game, but some of the block puzzles are quite challenging if you are coming at them for the first time. It's also quite fun to play with a friend since you can interact with each other, throwing items and stuff. It's a very different experience from playing solo, whic is also ver cool.