What I like to do is give my group a brief idea of what is in our world and let them create for themselves. I'm VERY open to their embellishing, but will not allow magic items, special powers, etc. I then talk to each player and "tweak" the character to fit into a certain area of the world. When we reach agreement, I let him (all men - SORRY) search out information about his region, politics, etc.
With respect to getting the group together, I have set up an Order of the Tree (historically significant), whose charter is to seek adventure. This gets rid of the uncomfortable "you meet in a bar" scenario.