Zelda Style Dungeon Crawl?

If you're just looking for generic puzzles to put in, and not dungeon specific ones that would rely on a separate player designing and implementing them, then I suggest looking at Mansions of Madness' puzzle system.

Basically, when you come up to a locked door, etc. in that game, a group of tiles are placed beside the board. These tiles could be a "slide puzzle" set-up, or it will be a center tile with different symbols on each side, and tiles coming off of those symbols. Then, players are allowed to rotate, swap, or discard-and-draw tiles a number of times equal to a particular character stat (in this case, Lore). It rewards players who actually play the game, and doesn't necessarily make the better characters win the game for you. It is also not an "unsolvable" puzzle, since you can always exchange a bad piece for a new one.

=================================================

Also, when I think of all my time playing Zelda games, there are two core themes of each dungeon besides the puzzles: unique bosses/final bosses, and unique dungeon-specific loot. The bosses could be random if you'd like, or maybe random from a subset of bosses. Perhaps, they roll a die at the beginning of the dungeon, and the "fire" result means they draw monsters from the fire deck, and they randomly get a fire boss at the end (out of 5 potential fire bosses, for instance).

The dungeon specific loot is in reference to how, in Ocarina of Time for instance, you get the Hookshot in one temple, and you have to start using it immediately in that temple. You also have maps and compasses in EVERY dungeon since the beginning of the series.

==================================================

A few ways to go about doing this game:

1) One-off adventures. Random Dungeon, random loot, random bosses, etc.

2) Chained adventures that are predetermined. This requires you to design the "campaign" while designing the game.

3) A "reverse choose-your-own-adventure". Basically, the first dungeon is random. After completing that, there is a book that the players reference that determines where they go next (i.e., "We just found the Shining Spear in the Fire Dungeon, so we look at this table and... next up is the Water Dungeon!"... then later "Turns out the Water Temple had the Helm of Truth, so now we go to..."). This would require a lot of work like #2, but leave the randomness (and replay ability) in the game. All roads would lead to the "final dungeon" where you use all the items you've collected against the end boss.

So, my vote is for #3, but it is the most complex** to design. But this is how games like Betrayal at House on the Hill, Tales of Arabian Nights, etc. get all the love they get.

**And you better believe this is complicated. I created a StarCraft RPG using the map creator for StarCraft, and every time you won a mission, it would check certain parameters to determine which mission to load next. There were so many variables I missed that my first playthrough it kept failing to load because no mission took EVERY contingency into account.