My favorite puzzle game is Catherine.
I don't really get frustrated by challenging puzzles. As long as I am given all the information and tools to solve it, more challenging can be better. If I cannot solve it initially, I will come back to it later. Catherine is particularly challenging because of it's timer. It forces you to be a slightly less considered, and instead react. The difficulty can be eased with an undo button, but it's optional, and not in the harder difficulties (I think just hard mode, but I've forgotten).
Moreover, there are usually multiple solutions to Catherine's puzzles. I'm just speculating, but I would imagine that allows a greater variety of people to solve the puzzles. You are not railroaded into a particular line of thought. However! This might actually be a detriment. If you are not railroaded into that way of thinking, some puzzles that expect you to have specific mechanical knowledge might be more difficult. I haven't looked at the puzzles closely enough to know if that could be a problem- it might not even be a bad thing.
All this is reversed in the Rapunzel mini-game within Catherine. There is no timer, and usually just one solution. Personally, I found Rapunzel a bit annoying, but I could picture some people preferring the mini-game.
A few other thoughts: I love Braid for how thoroughly the mechanics are explored, and the step-wise difficulty curve/process of learning the mechanics. I felt similarly about The Swapper, and Portal.
On the otherhand, I felt The Talos Principle, had some fairly weak puzzles. It is hard for me to say why I felt this way. I think it is because the mechanics did not feel novel. I rarely felt like I learned anything new solving a puzzle. This goes for Limbo as well. The mechanics lacked depth and innovation for me.
The Talos Principle is also in 3-D space, and in first person (by default). Solutions would sometimes just appear from looking at different angles, which I find boring. Two-dimensional games tend to present you with all relevant info at once. Portal was in 3D space, but because the entire puzzle was manipulating your way across space, it gets away with it.