Good news! You have everything you need to get started. The new Red Box is self contained and can get your group up and running for several sessions at least.
The included adventure will get the characters up to 2nd level. In order to obtain higher levels you will need Heroes of the Fallen Land. This also contains the full rules that the player needs.
An experienced DM will need nothing further. However, a Dungeon Master's Kit would be most helpful to get the complete rules as long as 2 more adventures which will get the characters up to 6th4th level.
That's it, that is all you need to play for 42-63 months (assuming a game a week). Once you get through that, your group will probably have a good idea of what is needed next.
- Heroes of the Forgotten Realms: More options for the players
- Monster Vault: More options for the DM :) (Includes a continuation of the mini-campaign up to level 6)
- One or more DDI subscriptions:
- Makes character generation much easier and more likely to be correct
- Frankly, I have a hard time imagining DMing without it. I remember that I used to, but I have no desire to go back to a time when I couldn't look anything up quickly :)
I don't think you need the 3 player's handbooks at all. You can get nearly everything out of DDI if you want more options for the players. The Dungeon Master's guides would be a good pickup for a less experienced DM, but there is going to be a lot of overlap with the Dungeon Master's Kit.
Before picking up those, I'd recommend investing in a few Dungeon Tile sets and perhaps some miniatures to supplement your counters.