I think one of the reasons that many people are recommending CoC (non-d20) is that Chaosium's d100 system is pretty easy to learn. Way back when, I bought their Runequest rules and had a game up & running within an hour or so (granted, I had already played D&D).
Chaosium puts out a "mini-book" called BASIC ROLEPLAYING for about $15 USD. It's more of a primer to gaming than a complete system though.
Another option might be GURPS. You can download the GURPS Lite pdf from SJGames for free. It has everything you need to play except the dice and GURPS only uses d6's.
Decipher puts out a "basic box" for the LOTR RPG which -if the burgeoning gamers are interested in fantasy- would give them some familiar characters and settings to learn within. The CODA system works on a similar model to d20 (roll the dice, add your bonuses, try to beat the "Test Number") and they've done a great job of capturing the Middle Earth feel.
Personally, I think d20 is a good system to learn from the start. It is fairly straightforward and plays quickly. GURPS is good too, but the GM needs to have a genre/setting in mind before you start making up characters, which means more prep work. I guess I'll cast another vote for the D&D Adventure Game boxed set.
BTW Chauzu, Hackmaster is based on the 1st & 2nd editions of AD&D. Which is not the same as Basic D&D. Easy to confuse, I know.
