Dr_Adder: I already know about the Diablos and Nethack. Are there any others out there? Can they be released on here?
How about Dungeon Hack? It was a Dungeons and Dragons game based on the Eye of the Beholder engine (I don't know the real name for it). The story is thin, somewhat like Nethack's. A sorceress grabs you and sends you into a dungeon to find an item. I forgot the item, probably the amulet of Rodney or something. The graphics where quite good for the early 90s. As for re-playability, the dungeons were random. I forget if the potions were randomized. Keeping yourself full was also on the required things to do, and perhaps torches were required. I still have it on floppies in the box on my shelf. When you died, your name was recorded on dungeon depth and score table. Since I save-scummed a lot, there was typically only one to two names on the table at any given time.
Strategy:
I can't imagine finishing this game without having spell-casting ability. My favorite was the cleric for a really simple 2nd level spell and long hallways, and of course, the "Identify" spell. Second favorite was the magic user for the same reason. Never got any lower than the 7th dungeon level with a fighter, then again, I consumed/read/used everything that fell into my hands: why would a monster carry around a tasty potion of poison!?