Thanks for the info guys, this is all good stuff. I will say, I'm a little surprised that the Starter Set has been recommended a couple of times. I bought the one for 4E (Red Box) and it felt very bare-bones. I don't really mean that it was lacking in Adventure/Fluff, I would expect that, but it seemed like it was even missing some rules type stuff. I'd have to dig it back out to be certain, but I thought it was literally a toned down version called "D&D Essentials" or something like that. Is the 5E version better in that regard?
The included rulebook is basically the same as the Basic Rules you can download for free, meaning it only includes a few core classes, races, and options. You already have the Player's Handbook, so there is nothing new here for you.
It also comes with pregenerated character sheets (which can also be downloaded for free) and a set of dice.
The real value of the Starter Set is the included adventure, Lost Mine of Phandelver, which is a lot of fun and very easy to run as a first campaign.