So, a bit more on how I typically start a campaign:
1) Three or four weeks before launching a campaign, I'll send everyone that has signaled they want to be involved a questionnaire about their past experiences with D&D, what modules they've played, what they enjoy in an RPG, and what sort of story they might want to be involved in. This gives me an idea if I should be leaning toward the more sandbox end of the scale, or to the more adventure path end of the scale. It also tells me whether I can mine published modules for ideas. It also helps me decide as a group whether they want to play a more heroic group, or a more villainous group.
2) About 2-3 weeks before we start play, I'll try to decide on what I want my major conflict to be about and what I want my starting hook to be. This is a basically a one sentence statement of the campaigns theme. It might be something abstract like, "Do the ends justify the means?" or "Are the gods worthy of worship?" Or it might be something straight forward like, "Defend the kingdom from the invading goblin horde." or "The Drow have returned to the surface!" I then try to imagine a huge compelling hook to start the game forward that sets the stage for that theme. I won't necessarily stay at that epic scale, but I want to start their so that the players are well and hooked into the game. In the past I've tried to do slow builds where I slowly unfold the central theme Les Miserables style, but players often get bored before they realize everything is tied together and what's really going on. It's best to open like a Summer Blockbuster. You don't want to wait 40 or 80 hours of play to get the player's involved.
3) During this period I'm also trying to get players to make PC's. A PC is a character sheet and some sort of background. The character sheet has to use approved chargen elements, has to be correct, and has to be at least viable. Basically you help the players without system mastery make the sort of character that is either what they want or which can become what they want, and you make sure the players with system mastery aren't getting so excited that they cheat. You also at this time need to start helping the player integrate the character with the campaign world and with the party. The biggest questions here are, "Why might you become a hero?", and "Why would you stay with these other characters?" You want to sure you have some basic motivation or compulsion to be an adventurer. At this time you can also start working on secrets, hooks, and nemesis you might want to work into the game. Often the player's desires will suggest elements to your campaign world that you've never thought about or which exist only as rough sketches that need to be detailed. The aforementioned "good aligned assassin" example was one of those for me. Assassin cults were invariably evil. When I first heard the player I wanted to just reflexively say "No". But I spent about 5 minutes thinking about it, and managed to come up with a heretical cult of one of the good aligned deities that had decided necromancy was such a completely evil thing that it justified rough vigilante justice to stop, and used the tenants of the main cult to justify that belief. So they went around assassinating necromancers, which fit with the story - since the main villains were heavy into necromancy and other black magic. Getting all the PC's made and approved is usually a two week process. It's best to do it before starting play. Don't ruin the first session by making it a PC making session, and do not expect to have a game work with players that have never played together just showing up with PCs you've never seen before.
4) If you are going to run a more adventure path sort of game, you need to come up with the broad story arc - who the BBEGs are, what they want, what they plan on doing to achieve that goal, how you anticipate the story is probably going to go, and what the main locations are going to be. If you are going to run a more sand box game, you need to decide on a suitably small scale setting that you can actual fill up with the time you plan on investing each week, and make a list of 16-20 conflicts that exist in that setting, and then get to the hard work of making a highly detailed map with as many cool features as you can imagine. You'll never have it detailed enough, and every week will find you making new granularity, but you have to start somewhere. Sandboxes are more work than adventure paths, with the basic difference being how much work you do that you know you'll probably never use (paths not taken). Don't try to sandbox a whole world. A thousand square miles should do it to start.
