I always found AMFV very underrated. Maybe I've never really been a puzzle person but I liked that one because it was more of an interactive story.

Also really liked Planetfall. Those three (along with Hitchhiker's) were all written by a classmate of mine who I knew quite well.