Trinity is hard as crap.
Er, maybe that's not such a good simile.
Trinity is immensely hard. Come to think of it, I never finished it. I recall getting to a point where I could explore different areas, but there wasn't much in the way of clues as to what I should be doing or what happened next.
Curses by Graham Nelson is another good one, on par with the best of the Infocom titles. (With one puzzle that is horribly poorly designed. But other than that, I mean.)
Beyond Zork and Zork Zero are lots of fun, if you find you like the GUE-niverse. Play at least Zork 1 and 2 first, though.
The non-Infocom title Zork: The Undiscovered Underground is also quite good. Again, one terribly wretched puzzle. Again, play Zork 1 and 2 first.
If you like the Zork setting (light fantasy), you may also like the various "Unnkulia" titles, as well as The Meteor, The Stone and a Long Glass of Sherbet. I've only dabbled with those, but they are highly regarded.
Conan Kill Everything is pretty funny.
Agree with the others, too... to play the Infocom games, you really need the inclusions in order to get through some of the game. Slick way of immersively doing copy protection.