The key to getting dungeon gameplay right is to engage rather than confuse or frustrate the player. "Puzzles," which in the broadest sense are defined as dungeon obstacles that do not involve plain combat, can be a very enriching part of the dungeon experience, or they can frustrate a player enough to turn the game off. There is nothing wrong with the premise of dunegon puzzles inherently.
I imagine that many people would say they like RPG puzzles that make them "stop and think" but "aren't too hard." Well, that's a load, really. "Stop and think" is a misleading idea altogether, and almost no one actually stops playing a game to think about what to do next. Usually we just muddle around the dungeon trying to find some clue or key we overlooked, getting increasingly angry when that strange-looking block won't move for the eighth damn time in a row that we try to push it, or when that frozen troll statue makes a sound whenever you step on a certain tile, but nothing else seems to happen. You know? A puzzle fails when people suddenly realize how limited their interface with the game really is. We say "If I were actually in there, I'd just..." but when all you've got is a controller and six buttons, connected to a simplified virtual environment where there is only ever one correct answer to a puzzle, then if you can't follow a puzzle's line of logic, then you're screwed. Then you go to GameFAQs and ask your question on the forums. Then they call you a n00b and trip over themselves to give you links to the FAQs. Then you look it up in a FAQ and the answer is so simple that it leaves you feeling empty and used.
The first big challenge for game developers is that many of the puzzles that are the most fun to design, are less enjoyable to solve. There's a very fine line between leading the player by the ear and giving no clues at all. The difference between a boring, mechanical puzzle that's far too easy and a horrible, confusing puzzle that's impossible to solve is extremely small, extremely subtle. The second big challenge for game developers is that different players enjoy different puzzles. I couldn't stand Majora's Mask because the puzzles took away from my enjoyment of the game rather than add to it, but I gather that many people actually enjoyed all that nonsensical running around, putting square pegs through round holes, and what have you.
Some developers say "Aw, fuck it!" and largely don't bother with puzzles. I had a great time with the Secret of Mana dungeons, because they didn't waste my time with bad puzzles. In fact they did very little by way of confusing puzzles or confusing layouts. Most of the game's dunegones were very short and to the point; I liked that. When you came across a long dungeon, it was fun because it was rare, hard, and something like a story progression marker--Elinee's castle, the Pandora Ruins, etc. Dungeons like those were a nice, long, hard slog with lots of enemies and no relief. A coupla' candies, a coupla' cups of wishes, and that's all you've got. The fun came from slogging your way through the battles, not knowing if you'd make it through, rather than unlocking some door with the twelve stones of power at the moment of celestial equinox...
But if you really want to tackle the problem and make an outstanding game, you won't just leave the puzzles out. You'll put in the best ones you can. And Chrono Trigger did pretty well in that regard. But I'll admit it didn't always succeed. The puzzle about Chrono Trigger that drove me the most crazy was...I think it was the Prehistoric island that appears as a sidequest late in the game, in one of the Guardia time periods. There's a room with a ladder in it, and I kept thinking there was supposed to be a way to get that stupid ladder to move down, but no. I was half insane with fury before I realized that you have to fall through the floor in that other room. (A cat shows you how to do this in the original Tyrano Lair; I had forgotten.) For me that was a terrible puzzle, because it was no fun at all and stopped me from progressing through the game.
Compare that with the puzzle in Chrono Trigger that I found the most boring...I think that one would have to be where you're onboard the Blackbird and you have to poke your way blindly around the air ducts looking to see which room is unguarded so that you can drop in and retrieve your gear. It was easy, but it took too long and offered no enjoyment along the way.
So what am I rambling on about? I dunno...just that I think it's not puzzles in general that deserve the blame when a player gets frustrated by one of them, but rather the nature of the obstacles they present, the clues offered as to their solution, the inuitiveness of that solution--that's an important one--and the execution of the puzzle itself.
