Personally, I've always been a fan of setting aside the first night to let everyone make characters and make sure that things go smoothly. That way, the players get to help sculpt the party the way they want it without it becoming haphazard catch-as-catch-can, and they can think of basic reasons to know each other through character creation.
Failing that, use the Shadowrun method. The characters are all professional troubleshooters/adventurers/mercenaries, they probably know each other by reputation if not from having worked together before, and they're all called together for a job. Might not be the most heroic or epic way to start a campaign, but if the players just want to get right to the meat of adventuring, this approach allows them to do just that with a minimum of fuss.