I also disliked the old point’n’click “puzzles” where you had to eg. use some completely random object on another completely random object to get ahead, and there was really no way to logically deduce what the hell you were supposed to do so it was just a question of using everything on everything until something happened. I’ve always been partial to how Cyan (makers of eg. the Myst series) does puzzles; nowadays it seems like puzzle games are really dumbed down and barely qualify as puzzles with the amount of hand-holding they do, but if I play eg. Myst or Obduction I pretty much have to use a notebook to keep all my clues straight.
So, I guess for me a good puzzle is one that’s actually challenging but logical, and I especially enjoy ones that tie together multiple different things from different areas of the game and aren’t self-contained, ie. you have to combine knowledge you picked up along the way to solve it.
So my preferences are maybe a bit more on the “hardcore puzzle” side, I guess. I just love a challenge.
The Myst games probably qualify as my most satisfying puzzle experiences, although I can’t really name any one specific puzzle.