With my design document relatively fleshed out, my mind is turning towards starting a prototype. As they say, the first step is always the hardest. This will be my first self-driven project, and that first step is looking awfully daunting. Does anyone have any advice on where to start? I know this is a very personal choice, but I'm interested to hear how more experienced devs approach that first step in development. For example, do you start small with something like the player movement and controls? Or do you prefer to set the stage a bit first by establishing a bit of the world space?

I think it's different for everyone, but I personally have found the following as a decent process that has resulted in things actually getting done:

1) Break your game down in phases.  Start with boilerplate/basic infrastructure that is necessary for the core of your game.  Next, work on the core mechanisms and features.  By that second phase, you'll have a lot running quickly, but as with most things, the devil is in the details.  Following "phases" should be about testing, tweaking, and incorporating those lesser features and mechanisms (assuming they've survived your constant review of eliminating that which is not necessary).

2) Within a phase, work on a feature/mechanism/task one at a time.  Set deadlines for yourself and a realistic amount of work for that time frame.  Bit by bit, you'll start building something more and more cohesive to your end goal

3) Constantly re-evaluate how things are going.  Be like water ( ).   You may find that it's quite difficult to implement certain features, and when you get down to it, they're not really that important to the game.  You may find simplifications to a system you thought up of before.  And with all that tweaking and testing that you should be doing sooner, rather than later, you should have a clearer picture of what needs to stay and what can go.

4) I'm not sure what your skill sets are, but if art and music/sfx/etc. are planned, get placeholders in ASAP (the closer to end goal functionality, the better), and in one of the earlier phases, try to get the artist, musicians, folely (sp?) artist, etc. involved early to integrate things.  You may find tools that need to be developed, or certain technical limitations that are getting into the creative forces' way.  Best to nix those earlier rather than later.  This may also affect what comes out of #3.

General-ish advice from an eternal hobbyist, so take with a grain of salt. 

I tend to work best with an end goal in mind and breaking it down into what needs to happen to meet that end goal (top-down approach).  Some people don't work that way.  So find what works for you.

Use your existing knowledge/skills:

I start by picking the tools I am most familiar with, to really only focus on quickly "getting there". Everyone might suggest you some tool, which might be good for fast results, but learning it while you want to get a prototype is a NO.

Rip existing stuff:

If you have already some code/art that partially does what you plan to do, just copy&paste it into the prototype. Even external stuff is better than spending time on creating something yourself. (You can always iterate and improve or replace it, if it does not fit your prototype, once it's running)

Coarse to Fine:

Don't do a classical "Task A, Task B, Task C..." route, instead: attack the biggest offenders. You are not planing to create a product, but to evaluate the viability of an idea. Hence nobody should judge the state of polish, but you should "polish" everything to the degree where there is something else that is more offending the state of your prototype. When you show your prototype to someone, you should tell what it suppose to validate and which part is just a dummy e.g. "The art is just made of boxes, as I only focused on the jump&run gameplay mechanics".

Throw it away:

It happens way too often that "prototypes turn into products", that prevents you at one side to go fully hacky&productive on the prototype, on the other side you might spent more time to clean up stuff "and get it right" than it would take if you started the project from a clean state. Hence, really try to make it a throw-away thingy. Don't fall into temptation to continue with it. There might be better tools, existing libraries, etc. which you should consider once the prototype is working.

Join a Jam (optional):

Taking part in e.g. ludum dare is like a prototype paradise. A lot of like-minded, a short crunch, you can learn productivity tricks (e.g. fire&forget tools like a "sound generator" that just randomly generates sounds: learning time: 1min), and when it's over, it's over.

Another option you might want to consider is the 'user story approach'. Create very simple scenarios containing what the player would do and write the basic requirements for that. Probably you will detect some additional features that are desired or required. Write those down with some priority (e.g. must implement now, when possible and so on). You can then keep on iterating according to the stories and urgent identified requirements.

Having an initial overview of user stories give you the ability to roughly plan the systems to accommodate future requirements without the need of being too detailed upfront.