Well designed puzzles, but I think the issue with complexity vs. difficulty is not necessarily contained in puzzle design, but in designing a new puzzle-type. For example, Jonathan Blow's game The Witness took him a considerable time to create a brand new style of puzzles, but even with his effort the structure of how the puzzles were solved required complexity to be added for continued engagement (Making the grids bigger, adding new mechanics), by comparison there was not as much room the expand the difficulty besides involving the scenery and player angle/position within the puzzles.
There are indeed puzzle games where it makes perfect sense to add complexity as the game progresses, and The Witness is certainly such a game.
My point is rather that it often is done without good reason, as if the puzzle designers thought there is no other way.
---
As for the move limit, I absolutely understand why it seems out-of-place. I had no move limit originally (because to me, like you, it seemed just pointless and annoying), but during some alpha-testing I noticed that a lot of players would just move around for ages until they solved it more or less by accident. I actually added the limit
by request of these testers, because they felt it was not very satisfying to just stumble upon the solution, but that it was hard to resist playing in that manner.
So while I see your point and would like to agree, after studying and hearing the opinions of many play testers, I'm also pretty certain the game overall would be less enjoyable without the limit.
Actually, during the alpha-testing, I kept movelogs of every tester so that I could study how they solved the puzzles. Almost every move limit is based on these logs, to cut off at the point where people statistically seemed to start just rambling, or to block some particularly uninteresting solutions.
I also noticed that when my play testers had a move limit, they approached the problem in a very different manner. They used a lot more reasoning, and a lot less just searching around. Having no move limit even inflicted on the way they looked for optimal solutions. Having the move limit made them play in a way that not only was closer to my own intentions, but also in a way that they themselves reported as more satisfying.