Here's something that I did for my Nobilis campaign that you may find interesting to try.
Character creation will be communal. Tell everyone to bring only a name, a personality, and a nifty background to character creation, but insist that they do not have a particular class or race or anything in mind. The background should be relatively generic; this is the point. At the table, everyone goes around and introduces their character and their background and so on. Then, you go around the table and put the spotlight on one player, and have all of the other players suggest classes and races and feats and skill choices or whatever that seem like they might be a good match. Possibly in this way they could arrange it so that their characters are interconnected, as well.
And then, at this point, everyone chooses a class and race, and then rolls stats for their character. (This will probably shed a different light on their background.) And then, well, it's character creation as normal.
Admittedly, this does require rather cooperative players, but you may find it useful as everyone feels invested in the party as a whole. My current GM has everyone declare class and race and then roll 4d6 straight down the list, which has also turned out interestingly.