Another vote for Nethack, wasted a lot of time on that game in school.
Yume Nikki is another good one, kind of like
LSD for the PS1. It's a horror game, but it doesn't try to startle you. All it does is put you in a world of vaguely absurd, surreal rooms and lets you explore.
Embric of Wulfhammer's Castle is a favorite of mine as well. While it was made in RPG maker and looks/sounds like a classic SNES game, it's more like a visual novel where you can actually control your character. Specifically, you play as the princess of the kingdom, and pretty much every female character is more than a little gay for you. Features multiple endings, tons of branching plot paths, some good writing and humor, etc. Also slightly NSFW, but absolutely not porn.