One important factor in a good puzzle game is that the difficulty does not just ramp up because of a trivially expanded solution space.
So say you have a game where you can walk four ways, and if you walk over switches doors open and close. The first puzzle has two switches, the 25th puzzle uses the same basic thought process but has 30 switches. But you're not really learning anything new, just doing the same thing but with a bigger solution space. A really good difficult puzzle would still only have about five switches, but requires a different tack of thinking to solve.
That's all very abstract, so to think of a puzzle designer I admire, look at some of Alan Hazelden's stuff, like Sokobond. (I don't like Sokoban-type puzzles, so me liking Sokobond must mean that he's a good enigmatographer
As you progress, you're not just building giant molecules on a giant board. You're still building little things like methane on quite tiny boards, it's just that about a quarter of the way into the puzzle you go, "No wait, this should be impossible. There's no way I can get that in there without doing that..." It looks impossible because you haven't yet developed the right kind of thinking to solve it. You hadn't yet caught on to the technique of, say, using your neutral "arm" of atoms to manipulate other atoms. You have to improve your thinking to solve it, rather than just do a familiar kind of thinking on an expanded solution space.
(On the other hand, there's also a style of puzzle game where the point isn't to think to hard, but to just zone out using a familiar set of mechanics. Like Minesweeper. People don't do a giant Minesweeper puzzle because they want a serious brain work-out, they just want to take a brain stroll. Or someone doing a big interlocked Sudoku or something. You just want something big that feels satisfying to solve, so that you can stay in a comfortable zone for an hour or two. That's a very different sort of puzzle game, though.)