I've learned that it's best to leave this up to the PCs as much as possible. They become more excited about it if they do it, and consequently are more into the game. I tried setting up a specific sort of dynamic by creating some common NPCs that each PC knew, and even though they were supposed to be lifelong friends with some of them, they had no compunctions in hating them, or abandoning them at the drop of a hat.
As a player, I kind of dislike the metagaming that goes on if the PCs don't have some connection ahead of time, but it's glossed over for the sake of gameplay. A good start to a campaign for me, would be one where the PCs get together in session one without any meta-gaming or strict character creation rules. Hard to do, but so nice when it happens.
I'm fond of taverns when starting, but that might be because our DM is so fond of blowing them up, or damaging something nearby in some way to start things off with a bang, and we still never know what it's going to be like.