Plaguescarred
Hero
I included a world map because it greatly helped us playing after we started with the Basic set (red box) and found one in the Expert set (blue box).
Original map here:
Original map here:

[*]Four miniatures representing characters/races and pre-made sheets.
I hope not. That, IMO, sets the wrong tone for new players. Miniatures should not be implied as the default means of playing the game.
DON'T include miniatures. They're just too darn expensive to go in a reasonably priced starter set.
If I can suggest a novel approach:
1) AN ADVENTURE covering 5 levels w/plenty of tips for newbie DMs
2) slimmed down rules
3) 8 pre-gens with instructions for leveling 10 levels & very limited options
4) cool maps and handouts
4) dice
You're not selling Dungeons & Dragons. You're selling "Dungeons & Dragons: Seekers of the Dark Flame" or whatever. You're selling the individual adventure, and if the newbie players like it, they have a couple of options:
1) Buy "Advanced Dungeons & Dragons" so they can make their own characters and adventures.
2) Buy the next adventure in the line (and either bring over your pre-gen or use one of the ones that comes with the next adventure)
There are a number of board games (including 4e's Ravenloft and Wrath of Aschardalon (sp!)) that provide set characters with leveling opportunities. Casual gamers get invested, even when they don't have the ability to fully create their character from scratch. To keep the basic game light, use the same approach: a set adventure with options to level/customize as you go. When they want more, THEN sell them the books that let them make their own characters and adventures.
Of course, if the Basic product skips over rules of weapon ranges, opportunity attacks / withdrawing, spell ranges/area templates and similar things... well then perhaps it can be done without a battlemat more easily.