You need at least one of the Heroes books, either the DM's Kit OR the RC, and since you still need the Monsters, the Monster Vault. The RC doesn't give you tokens, maps or modules, but those weren't things you wanted in your list. The Heroes book has magic items in it, nothing really stellar but enough to get by for a bit, and to give you an idea of what they are so you can create your own.
Yeah, it also depends on what he means by a "complete game".
With just the Heroes book and the DM's kit, you have an adventure, enough magic items to be able to give out a decent variety of magic items, as well as all the monsters you need to run that adventure, the maps and the tokens to represent all of them.
If you wanted to make your own adventures after that, you have everything you need except the monsters. Then you'd have to buy the Monster Vault.
That pretty well covers it.
Heroes of the F'n Lands has character creation/advencement, basic skills and combat rules, and some magic items. Presented from the player POV.
Dungeon Master's Book (DM's Kit) has detailed combat rules, skill challenges, traps, some more magic items, and lots and lots of DM advice regarding setting, story, meta-game, encounters, etc. Presented from the DM POV.
Rules Compendium is a comprehensive rules reference, including detailed skill and combat rules, but no 'catalog' content (feats, powers, items, monsters, etc.). Presented from a neutral reference POV.
All three books contain some overlap, particularly for skills and combat, but each redundant instance is written from a different viewpoint and level of detail. The player book has only has brief coverage of combat basics so players understand the character options, the DM book has detailed combat rules with advice for running combat at the table, and the reference book has every nook and cranny of combat listed without any other context.
Players will need at least one of the two player books, that's a really straightforward requirement. So that's $20 (-discounts) right there. Players can also benefit by having a copy of the RC handy, but that's optional.
The DM will need either the RC or DM's Kit at minimum. The DM's Book contains stuff from both 4E DMGs, and is mostly redundant with them. The RC and DM's book do have rules reference overlap, but the presentation is very different. If you are an experienced DM, and either own the 4E DMGs or don't need that kind of advice, you will get better mileage out of the RC. That's another $20 (-discounts), and you're done (except as noted below).
If you're a newbie DM, $40 (-discounts) for the DM's Kit will get you a ton of useful advice culled from both previous DMGs, two levels worth (2nd-3rd) of good adventuring material including a mini-setting (Barony of Harkenwold), and all the extra swag (token, maps, screen). The RC is again pretty handy, but optional. However, if $40 is too steep, and you think you can swing a game with web freebies and such, the RC might cover your needs in a pinch.
The real problem right now for DMs is MONSTERS. The RC is cheaper, but at least the DM's Kit has the monsters contained in Reavers of Harkenwold. A month of DDI will net you the current Monster Builder catalog, but that's not an 'essentials' solution. Monster Vault can't come soon enough for an Essentials DM. Again, this might be less of a problem for an experienced DM, but the newbies will be hurting. Still, I remember 3E's rollout in 2000 when we had to wait two months for the MM release, so this isn't much different.
