After slogging around Visual Studio I finally figured out the answer that took far longer than it should have.
In order to take an existing project without source control and put it to an existing EMPTY (this is important) GitHub repository, the process is simple, but tricky, because your first inclination is to use the Team Explorer, which is wrong and is why you're having problems.
First, add it to source control. There are some explanations of that above, and everybody gets this far.
Now, this opens an empty LOCAL repository and the trick which nobody ever tells you about is to ignore the Team Explorer completely and go to the Solution Explorer, right click the solution and click Commit.
This then commits all differences between your existing solution and the local repository, essentially updating it with all these new files. Give it a default commit name 'initial files' or whatever floats your boat and commit.
Then simply click Sync on the next screen and drop in the EMPTY GitHub repository URL. Make sure it's empty or you'll have master branch conflicts and it won't let you. So either use a new repository or delete the old one that you had previously screwed up. Bear in mind this is Visual Studio 2013, so your mileage may vary.