Wizandry comes to mind, since it's one of the inspirations for both DQ and FF. You can try your hand at Megami Tensei but it's more post apocalyptic if that's not a problem. Both are NES/Famicom games.

For the SNES, most games really started to take after Final Fantasy IV and Phantasy Star in this era, so you lose out on some of that freedom to just go where you want. You can always play the fifth and sixth installments of FF and DQ from this era as both are still fairly non-linear after a certain point in their plots. Breath of Fire is an interesting choice that kind of opens up about half way through.

If you don't mind a genre shift, Ogre Battle: March of the Black Queen is a semi-non-linear title where you eventually have to choose different battlefields to continue the story which affects who joins and what ending you'll get.