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.