Nobody has mentioned Starcross but I thought that one was pretty fun. It had
a sort of generic sci-fi story, but the puzzles were interesting in that
they involved using the same items repeatedly in different situations, in
different ways... remember those teleporter discs? (As opposed to the usual
"key/door" situation where the bucket is just a red card key and the well is
just the red door, and when you tie the bucket to the rope so you can dip it
into the well and get whatever's in the bottom, that's just you using the
red cardkey to get through the red door. You know what I mean.)
Also I thought Hollywood Hijinx was fun, if somewhat arbitrary. Who can
forget the Atomic Chihuahua From Hell mini-game? (though that did have the
problem of "screw up, and you must reload, and you definitely will screw
up").
-J.
http://www.quartertothree.com/game-talk/archive/index.php/t-2972.html