I've been using the Dresden Files RPG setup system a lot lately, where you just do character / setting creation as the first session (note I don't play FATE, but the setup is easily portable). Basic gist is:
1) Each player makes a name and High Concept for his character. Fills in a super thin backstory (where / why / who), like two or three sentences tops.
2) Each player passes his sheet to the left (or right). The sheet you get, you write a little 2-3 sentence narrative about the time your character and the one you're borrowing met and had a little adventure or whatever.
3) Pass to the left again (assuming >3 players), rinse repeat step 2.
4) Get your sheet back, add in another line or two about recent events in your character's life, and maybe tidy up for cohesion.
5) Reading over the backstory, add a 2nd line to the high concept that has to do with a major Weakness, Flaw, or Trouble.
If using it in FATE, each of the 5 steps produces a mechanical Aspect that's used in the game. I don't do that, but I do encourage players to take skills and abilities that are logically tied to each of the things. It also helps to list the relationships produced by the shared history bits, like "Me and Skell are a good team", "Rodney Rogue is a douche", etc. Helps with RP.
Then you can do basically the same thing to flesh out the setting. Like, for instance, each player makes up a location with a location concept, pass to the left, add, pass to the left, add, etc. Same thing works for NPC's. Helps the weaker / newer players especially with getting into the groove, and saves a little work for the DM to boot.