I've recently replayed many of Jon Ingold's games, and I am very impressed with his writing. This game is probably his best story. There are some puzzles, but you are generally held by the hand and walked through them (except at the beginning, but the game basically gives up and lets you through if you don't get it).
The real puzzle in this game is trying to figure out what is really going on. Ingold knows exactly how much to say to make something cool and how little to say to keep your imagination interested.
This is a fantasy (and possibly sci-fi) game following an assassin who is trying to escape his hanging. Not only do you the player not know what is going on at first, your character doesn't either! Your mutual journey of discovery makes the game exciting.
If you get stuck on the first puzzle, don't sweat it. This is a story, and the puzzles are just side thoughts. If you prefer puzzles but enjoy his writing, Jon Ingold's Muldoon Legacy is a huge puzzle fest, much bigger than Curses! or MIT Zork.