Here are a few ideas to get us started that in my opinion are relevant. Feel free to add to or argue with them (I fully expect lots of disagreement, as everyone has different ideas about what the game means to them)
Good things:
- Simplicity (fewer things to break)
Going up (or across) is better than going down (requires more work on the part of the player, rather than just using gravity)
Ambiguity (There shouldn't be one single obvious solution)
Open spaces (require the player to build)
Not so good things:
- Complex machines with a few pieces missing (Usually too obvious to be challenging, although the inordinate fiddling to get the solution to exactly match the author's can be frustratingly time consuming. Plus they can often be solved cheaper by entirely bypassing all the author's hard work)
Constructed Obstacles (Vulnerable to being broken by a ruthless player)