The problem with most of FFXIs 'puzzles' was the lack of 'playing' with them.
You couldnt get ur hands dirty, and just mess around with a puzzle, until u got it right.
Most required other people to just kill things, or run from point a, to point b.

And when you are with other people, MOST of the time, THEY don't want you wasting their time, and will leave or quit if you didn't just look up the right way.

Puzzles like FFXI are still slightly welcome, for change of pace, BUT for the "Zelda feel" the OP might be suggesting, it would require some 1 player content in mind.