The basic three books -- Player's Handbook, Dungeon Master's Guide, and Monster Manual -- will give you what you need. You can find hard copies if you look online, possibly as a gift set. If you're experienced with other editions, you'll notice the lack of barbarian, bard, druid, half-orc and gnome options; those were included in Player's Handbook 2, and psionic classes of note, particularly the monk, were the focus of Player's Handbook 3.
Be aware that there are a fair number of rules updates that affect these. You can find the full list here.
For the Essentials line here's the breakdown of what I think you'll want if you go in that direction: the Dungeons & Dragons Fantasy Roleplaying Game Starter Set, as an optional tutorial; the Dungeon Master's Kit, which is the equivalent of the Dungeon Master's Guide; the Monster Vault; and one or both of Heroes of the Fallen Lands and Heroes of the Forgotten Kingdoms, which give player options. The first three of those were boxed sets, and you'd wind up with three or four adventures, some dungeon terrain tiles, a ton of tokens to use instead of miniatures, and a DM screen; these things are not included with the digital releases, however, so you might need to turn to external resellers. You may also want the Rules Compendium -- it has some rules not covered by the DM's Kit, but is more of value to people who have the core books and don't want to look up errata to rules.
The advantage of Essentials is that it's an easier entrance point, particularly if you're familiar with an older edition. Also, it doesn't have a ton of errata.
If you buy either group of books and later want to use material from the other group, that should be possible without any fuss.
Finally, I'll agree that the Dungeons & Dragons Insider subscription is a good purchase. You did get (in 2010) access to an online database containing every rules option from every source; you get a character builder, which also has all the options (Windows and Mac only); and you get daily articles. (2021 update: subscribing to DDI is no longer possible and the content needs to be picked up piecemeal. Dragon magazine is still available)
What do I need to do to be prepared to DM? I'm terrified I'm going to screw this up and turn off these boys from D&D
You need to read through the rule booklet, the Lost Mine of Phandelver adventure, and be ready to roll with whatever happens and have a good time.
The Starter Kit comes with 5 pre-made characters, are they standard or are the pre-made characters random?
They're standard ones for the adventure. Starting with them is probably a great place if you're not sure where to start.
If you want more options, you can download more "pregenerated characters" from the publisher's web site. (You can also download the "Starter Set Character Sheets" there, so you can print them out again in case one of the ones in your box loses a battle to a can of soda or you end up wanting to play the adventure again after you're done.)
If your players really want to customize everything, you can get the online Basic Rules and work through the character creation rules. I'd really advise against this approach, though, until your group is more familiar with the game. There's a lot of choices, and you need to play for a while to get a feel for things.
If the characters are standard where do I find the miniatures for them?
Maps? What the heck? Do I need them/Should I use them? Where do I find these?
There are two main approaches to playing D&D (and options in-between): The first style is generally called "theater of the mind" style, where everything is just in your collective imaginations. The DM describes the action, and players imagine how their character would respond. You occasionally make judgement calls on whether somebody is close enough to be within range for an effect, but there generally isn't much of a focus on exactly who is where. The second style is more tactical, where you track where each monster and player is more precisely, generally using miniatures. Either approach can work great. If you're new, I'd suggest starting with theater of the mind and seeing how that works before going to buy maps and miniatures, unless you know that what's going to interest your group is playing with little miniatures. The adventure booklet has maps in it, but that just can be to help you visualize how big things are and what's where so that you can describe it to your players. Don't worry about exact locations of things unless you really want that more tactical approach.
If you really want to try out the maps and miniatures approach, find a grid to use (It can be something simple like printing out some sheets of 1-inch squares, or something like the back of some kinds of wrapping paper), draw rooms on it with pen or marker, and use random objects you already have as tokens (coins, Lego minifigures, pawns from other board games) to represent the player characters and creatures in your battles.
If you end up really liking the miniatures approach, you might want to get a dry-erase or wet-erase grid board. Wizards of the Coast publishes their own D&D Adventure Grid, but there are a variety of options from other publishers as well. (They don't need to be D&D branded, you're just looking for something with 1-inch-or-so squares that can be easily drawn on and erased.) As for miniatures themselves, there are similarly a lot of options from a lot of publishers, in a lot of price ranges. One option is just little cardboard squares that just show a position on the board. Another is full-fledged miniature figurines, generally made of plastic, pewter, or metal. (Some people enjoy a hobby of painting these as least as much as they like playing the game.) I recently bought the Arcknight Flat Plastic Miniatures DM Starter Set, which has printed graphics (including I think every creature you'll meet in the Lost Mine of Phandelver) on little plastic sheets which pop into little stands, giving a bit of three-dimensionality while not having the cost or taking-up-space-on-my-shelf that full miniatures would have. But all of that is "extras" I'd only recommend if you're looking for more things to get and if everybody's going to like using them; it's certainly not needed at all in order to play and have a great time.
Some people use digital maps, either because they're playing entirely online, or they use a large display or projector on or near their table and track monster and player positions on their screen. For Lost Mine of Phandelver specifically, the illustrator has digital maps of the adventure available for sale intended for this use, though one could print them out too if one wanted to mess with getting the scaling right and either put together multiple papers or find a large-format printer. Again, this is an option you don't need at all, but since you asked about what you might want to buy or use I wanted to include the possibility for completeness.
But even though I just spent a lot of words describing various ways of using maps, really, doing everything in your mind will work great. Only use something more complicated if your group will find it more fun and worth the cost.
Anything else I should buy?
The premise of the Starter Set is that it has everything you need to get started, and it really does. You may want more sets of dice, just so you don't need to keep passing the ones in the set around the table, but it's not really needed to start.
Tips? Suggestions? I would like to introduce this game in a cool way. I figured I would set up the table in the middle of our rec room, buy some pizza, dim the lights, possibly dress-up, etc.
Sounds like you're off to a great start. Feel free to check out our chat room, browse questions here (see the new-gm and lost-mine-of-phandelver tags in particular), and look elsewhere on the Internet for tips, but really just don't worry about "screwing things up". Since sure you will make mistakes, and you'll discover things you wish you'd done differently, but the point of the game, like all games, is to have fun. Work on telling a fun story as a group, and don't let worrying, perfectionism, or even the rules get in the way of doing so.
Best Answer
It depends on what you're looking for
You're comparing two entirely different products.
Starter Set: I have no idea what D&D is and want to DM
The Starter Set has everything you need to start playing. It has a bunch of pre-made characters, it has enough of the rules to get going and it has a short campaign to play through. If you simply want to get started with D&D and have some friends who want to play, this is the easiest way to get going.
Dungeon Master's Guide: I know how to play D&D and want to make my own campaign
The Dungeon Master's Guide is just that, the Dungeon Master's Guide. It has no rules for players (those are in the Player's Handbook, almost all basic rules are in there, including character creation, how skills work, how you attack, how spellcasting works, etc.), there are no monsters (those are in the Monster Manual), it only has a lot of rules and advice on creating your own campaigns. It'll do little to teach you how to play the game. I mostly tend to open it to look up magic items or to look for variant rules to try out.
My recommendation:
As somebody who has DMed a lot of D&D, I can safely say that the Dungeon Master's Guide is a great resource, but not for somebody who has no idea what D&D is, at least not by itself, because it'll do nothing to teach you the game. However, if you're already familiar with D&D and want to make your own campaigns, the Dungeon Master's Guide is the better choice of the two, as the Starter Set does not explain how you can balance encounters or what variant rules are solid choices, it just explains the bare details.
In your case, it sounds like you don't even have the Player's Handbook, so the Dungeon Master's Guide would be a terrible first purchase. Go for the Starter Set and play it with some friends to learn the game first, or start by buying the Player's Handbook and playing as a player in some games.