A good puzzle should fuse with the game world, and not stick out like something that has no logical reason to exist. Legend of Grimrock is a good example of this. Love the games, and the puzzles themselves are very good from a grey cell standpoint, but teleporters in the middle of the forest, and various gate, trapdoor and pressure plate contraptions needed just to open a god damn door, just don't make any sense. The whole "evil wizard set it up this way" doesn't cut it as an excuse.
I also think puzzles generally should be larger than their immediate locate, and contain hints and clues elsewhere in the game world in a logical manner. I recall a Skyrim puzzle with some pillars that had to be turned a certain way, which actually had the book with the solution lying on a fucking podium in the exact room where the puzzle was performed!
If a puzzle is to be logical, it needs to be considered from the puzzle maker's view as well as the solver's, which in most cases means the maker doesn't actually want the puzzle to be solved (his secret lair being discovered, or whatever). In other words, it can't be too obvious a puzzle at all. No big pressure plate room that screams "solve me!", but small details that you need observation and thought to catch the very existence of, with subtle hints to their existence elsewhere in the game world. Preferably this is done with more than just loose journal pages, which is the usual lazy method (again, a logical reason must be provided for why someone would actually write clues in a journal and then rip the pages one by one, and place them in certain locations). Grimrock 2 does this pretty interestingly with the talking heads, though it's still just a variation of the journal page method.
