Well, posting here seems like a good idea to start with!
Hmmm. Not that I have occasion to recommend much IF, but if I did, I’d probably suggest that first they tried Parchment, which runs in the web browser, and so there’s no need for a separate interpreter download. The list of games on that page seemed fairly comprehensive, if a little old.
Of course, some people have lousy net connections, have to pay by the byte, or simply prefer to run things locally. I guess in that case I’d recommend Gargoyle which was updated just this month. It runs quite a few formats:Agility, Alan 2 and 3, Frotz (glk port), Glulxe, Hugo, Level 9, Magnetic Scrolls, Scare, Tads 2 and 3. Although it doesn’t explicitly say so, if I understand correctly, anything that runs Glulxe will also run z-code.
I just fired up my copy of Gargoyle (2011.1b-1) and checked: it definitely runs .z5 files. I also think this terp’s by far the nicest display to look at.
Only if someone wanted to run a particular game which both Parchment and Gargoyle won’t run (perhaps because of art resources, or just computers being their usual, obstinate selves), would I start thinking about other platform-specific interpreters.
EDIT: Gargoyle link updated (thanks @zarf), and also discovered that the parchment page 404s
EDIT2: But the links to parchment from the IFDB work. Perhaps a page with a list of newcomer-friendly games could use that mechanism?