You would enjoy pretty much all of the games by Zachtronics, including Infinifactory. They're all puzzle-oriented though, as far as I know, rather than sandbox.
Seconding Zachtronics; TIS-100 is an amazing game.
It's hard to call TIS-100 a "game", it's more "fictional, slightly gamified IDE"
Potato, potato. :)
Hmm, it might not be "full sandbox", but they are... flexible puzzles, which can be solved in various ways with different tradeoffs or optimizations.
I think that distinguishes them from other kinds of puzzle-games where you're hunting for "The One Predefined Secret" to make your solution.