I’ve added a list to IFDB of games that would be great for beginners: http://ifdb.tads.org/viewlist?id=gauovl7luodzkkf0 . The list contains a short spiel and you can click on the games to play or download the games.
[Edit by Mod - new link further down]
The first ten are web-based games, and the next twenty are parser-based (where you have to download an interpreter program, and you type commands).
I tried to pick a variety of genres, lengths, publication years, and difficulties for the games, although fantasy dominates the parser games. All of them are fun and simple at first, although some get pretty hard later.
I’m sure I left off some games that others think would be great for beginners (such as Kerkerkruip), so if any of you guys have your own lists of great games for beginners, you could add them in the comments or another thread.
(Edit: This list has now been deleted).