What is the difference between the Starter Set I can buy from my local store and the free Basic Rules I can get for free from the Wizards website?
Edited on 12/24/2014 to reflect release of the 3 core rule-books.
5th edition's Starter Set is decent to give you a feel for the basic rules, and outside players are not necessary. It is designed with beginners in mind, and is thus a good intro to the game. The starter set has an adventure in it that goes from level 1 to 5, while covering a lot of ground from a role-playing perspective as well as a combat perspective.
It's 20 dollars, but there's a high likelihood that most things outside of using the basic rules to create a character and joining the adventure league as a player are going to cost you more.
It does give you enough to work with to create your own campaigns as well, as the monsters in the appendix are varied enough for some play-room.
This is particularly advantageous if you don't have a lot of people in your current group and want to get going. If you just combine two groups, you might make the new group too big to manage reasonably. If there's only a couple of you it is easy and would likely be a great intro. If you have a single player you can draw in to play or DM that knows a lot about the game, it can certainly compensate on either side.
The basic rules are available on the official D&D website. They cover character creation for one of each type of fighter, cleric, rogue, and wizard as well as an assortment of backgrounds. The basic rules are free, and include monsters and magic items in the Dungeon Master documents. They won't tell your DM how to prepare a game outside of managing encounters, but it is enough to get you moving for free if your DM is willing to put in a little work.
As of the time of this update, the three core rule-books are available for purchase at online retailers and local game/hobby-stores.
The Player's Handbook (PHB) covers all of character creation, including far more options than the basic rules and documentation of the rules necessary to play that is more in depth than the basic rules (except in combat, which was covered very well in the basic rules). It is about the price of a new computer game (40-60 USD after-tax depending on where you get them). A game benefits highly from having this book, and most players end up getting one for themselves at some point.
The Monster Manual (MM) and Dungeon Master's Guide (DMG) are more for the DM. The former includes a huge assortment of monsters, beasts, and NPC templates ready for use. The latter is primarily about customizing your campaign, tuning and tweaking it for the way you want to play. The DMG also covers magic items, random dungeon generators, and a host of other resources that can be useful to someone running a game to speed up preparation and allow for customization. Typically only one of each of these books is necessary in an entire gaming group, but with the basic rules for free, the investment can wait until you are ready for it. Each of these two books costs the same as the PHB. Some groups pitch in together to split the cost for these two books, just make sure there won't be problems with book ownership after it's all done.
If you are in a hurry to try it within the next 3 or 4 weeks, then by all means pick up the Starter Set, or find someone at your local game store that has it and wants to run a game. Ultimately, the decision on how to approach this is up to you. There is no wrong path to start the game.
As far as official WOTC character sheets go, all can be found at this link. However, other than the ones you've linked, all the sheets contained there use the full ruleset. Not to mention none contain any story hooks to the Phandalin adventure.
As far as I know, there are no readily available pre-generated basic ruleset character sheets beyond those which you already have.
If you'd like to not waste time and don't mind a few of your players going beyond the basic ruleset, this part of the link above provides various characters with pre-generated sheets for up to lvl 10, far further than you'll need to finish Phandalin.
If you want to stick to the basic rules, you can always use a few of the sheets multiple times. The starter set is only meant as an introduction anyway, to be run up until lvl 5, so your players shouldn't be too bothered with having similar characters. If you choose to have more than two Fighters, you can actually add a bit of diversity by choosing different Fighting styles.
As far as background and personality go, the story hooks presented with the characters you already have are entirely optional. I've played the cleric with one group and am currently DM-ing with another, so I've got experience from both sides. My advice is to let your players decide whether they want to keep the existing background, personality traits and story hooks or create their own. With your more imaginative players making up their own stories, you should have no problems reusing some of the characters multiple times.
In the first group we all chose our own backgrounds and ended up having almost no story hooks left (except for the cleric's relation to the Rockseers). We also had two Wizards in our group, and it worked fine. We still had a lot of fun :) The Wizard is a pretty versatile class already, and their personalities were so different that it didn't at all feel like the same character was used twice.
For the second group, I've offered the players to change whatever they want, but seeing as they were all completely new to the entire concept of D&D they mostly went along with what was written, only changing a few personality traits. As a result of retaining the story hooks, this group has had more success finding/completing various side-quests that can be found in Phandalin compared to the first group. They've had a bit more trouble role-playing the characters, but they got used to them and are having lots of fun themselves :)