If you do have an idea, you should get to work on it ASAP. There is no better time than now. The longer you wait, the more likely it is that someone else is going to implement your idea and execute it well before you even get started.
If you don't have an idea, then finding an idea should be your first step. You can't really focus on picking up certain skills unless you know what you're going to accomplish. On the other hand, if you know you want to do a web application startup, then you should start learning PHP, Ruby on Rails, etc. right now.
Moving is a tough one. Don't discount your network of friends and family in your current city. They provide a lot of support and friendship that you will have to do without while you settle into a new city. If you live in or near a large city you should look for networking events aimed at startups. Startups love to present their product, and it's a great environment for meeting like-minded people. Check LinkedIn for groups in your area.
On the other hand, if you were already looking to move then the change of scenery could be just the thing you need to shake your life up kick you into startup mode. Also, you won't have any pesky friends or social engagements to occupy you for a while after moving, so there's even more time to work on your code. Really, though, you just need to pick a big city that you enjoy and can afford. Definitely visit several cities first and spend some time there before you make a decision.
Most importantly, however, you need to remember that planning and thinking are great, but doing is what gets things done. Focus on doing.
As for moving, I've always been told that you need to be in the Valley to be able to do a reasonably successful startup. How much of it is true? I live in Seattle, and there's a pretty good (albeit small) startup community here.