[After a brisk nap]

This is interesting. The discussion has finally made me understand what people mean by "exploration" as a separate element of adventure game design besides puzzles and story. (Or at least it has given me a notion of exploration that makes sense to me.)

I tend to think of the issue as how integrated the puzzles are with the story, the extent to which they are disguised as "normal" interactions with the world. If the game effectively pops up a message "Here is puzzle. Solve it!" then the puzzle isn't hidden at all, but if you have to go and discover it for yourself, then it tends to feel more organic to the world. To me this is the distinction between a puzzle game and an adventure game.

For pretty much all good puzzles, I think there should be clues somewhere in the game that tell you, or allow you to work out, what you are supposed to do. So it's a matter of how obvious and immediate those clues are: how much exploration and reasoning you need to do as a player to work out what the puzzle is. And that's not a binary either/or choice, it's a continuum.

In the example in the first post, you can have the game (or another character, which is the same thing except it avoids breaking the fourth wall) immediately tell you that you have to pull out certain books in the book case. Very obvious, very immediate.

Or the game could tell you the same thing, but only if you initiate a conversation with the other character. Still obvious, but slightly less immediate, since you have to "explore" the available actions a bit to discover that.

Or you might have to initiate the conversation, and then navigate a conversation tree before you get the explanation. Once you're told about it it's still obvious, but now there's a kind of simple dialog-exploration-puzzle you have to solve first (and arguably there should be a clue to let you know that you need to interrogate this other character, to provide motivation), so it's even less immediate.

Or when you talk to this other character, they don't straight out tell you there's a secret passage you operate by pulling books out of the book case, but give you a more indirect clue. Then you have a clue that isn't presented as an instruction or obviously useful information, but disguised as something mentioned in passing, for example. That makes it both less immediate and less obvious: you have to notice that it's there, and you have to think a bit to work out what it implies you should be doing.

Finally, instead of having one big clue that tells you about the puzzle, you could have a number of clues scattered around the game, that you need to combine in order to work out what they mean. For example, a character could tell you how the person who built this house loved riddles and built a secret passage somewhere in the house, a book about riddles in the book case could have a note that mentions a passage in the bedroom at the head of the bed, and some detail in the room could show that this room was originally the bedroom, and that the bookcase must be standing where the head of the bed used to be. Now the clues are neither immediate nor obvious: you have to explore extensively to find all the clues, you have to be alert in order to notice them and realize that they are important, and you have to do some significant reasoning to put them together.

So at one end of the spectrum you have an element of a puzzle game: it's obvious what the puzzle is, and you just have to solve it, but it isn't natural or integrated with the story, just an arbitrary obstacle. At the other end you have an element of an adventure game: instead of just solving a logic puzzle you are taking on the role of a character in a story, problem-solving and interacting with a more coherent world. But at the same time, you have to do quite a lot of work just to figure out what direction you should be looking, and if you miss one of the clues (either because you didn't find it, or because you didn't realize that it was a clue) it's possible to get stuck in a much more frustrating way, where you have no idea why you're stuck.

Like, I think, most other adventure gamers, I find the more organic, subtly integrated puzzles more rewarding, although I think it's nice to have a mix of puzzles that are more in your face as well. And I do think that the more you disguise your puzzle to not be immediately obvious as a puzzle, the higher the risk of players getting irretrievably stuck becomes.