I love non-linearity, it's just the
backtracking in Metroid... In LoZ, you had an objective, and once the dungeon was cleared, you're done. No need to go back over the same area over and over again.
If you like non-linear Zelda, you're gonna like A Link Between Worlds. Have you played that game?
I have not, but I've read a lot of good things about it. When I finally get my gigantic backlog finished, I'll buy it.
Speaking of backlog, I'm currently playing EarthBound. That game really isn't a hand holder, but it does give hints about where to go next... For instance, there's one part of the game where you have to find a yogurt maker, but it's lost. You find out where it is, but not
how to get it. It ends up being a big fetch quest, but it's the only one I've encountered in the game....
I also just can't get over how nonchalant the game is at times. I've laughed out loud several times. The enemies... locations, music, it's all superb.