What really got me was that the games encouraged something like hand-optimizing the size of your program. The levels were open-ended and the solution could be anything, but each solution has a cost, for example, least number of gates used in Robot Odyssey. In SpaceChem, it's number of symbols. In The Codex of Alchemical Engineering, cost is measured in total number of instructions, which encouraged solutions involving many different parts moving perfectly in sync. Those solutions were really difficult but rewarding to craft. However, cost in Opus Magnum is measured in total cost of parts (not instructions) used. That's less interesting to optimize, since the 'best' solution is often one part doing all the work (easy to optimize for), which in my opinion makes it a little less fun to play. Similarly, I remember the last few levels of Robot Odyssey didn't have much space in the way of optimizing (there is just one Correct Solution) which was underwhelming.
I guess my point is that the games were fun not because I had so much freedom in how I can finish each level. Rather it was the difficulty of optimizing each solution that attracted me. And it's hard to find games like that outside Zachtronics.
If you open up a least-symbol solution for Codex you'll find a lot of interesting tricks used to reduce symbols. For example, grab-left-left-release-left-left can be accomplished with just grab-left-release-wait, if you sync it so the released atom is removed by another arm at exactly the right time. It's a nice feeling to successfully shave off even one more symbol using these hacks!
In Opus Magnum, there are a lot of interesting things you can do to get more parallelism going in your solution. Except that, again, "fake" difficulty is added in the form of restricted inputs. Maybe I could build the molecule faster with two sources of water, but I only have one, and one source can't produce more than one particle per two cycles. The parts with costs are unlimited -- they just count against your cost. Source and sink parts are "free", but limited in bizarre ways. So much for the parallel approach I wanted to try. :/
I got to the last level on my own and learned a TON about logic gates. Maybe it's why I'm in robotics today.
The point I want to make is to never underestimate the capacity for children to learn and never assume something's too difficult. You don't have to get far for it to be a worthwhile endeavor.
Spacechem gave me a strong feeling of nostalgia for Robot Odyssey. It was very difficult. Didn't hold your hand. And was totally open ended on how you solve problems. Which results in feeling incredibly fulfilled when you do solve a puzzle. That feeling was what hooked me. I was so proud.