I'm very much a fan of a starting the party into some in medias res situation where they already know each other.
In some of my last few games, I've had:
1) Two groups of special military operatives for two recently allied nations, joined together in a task force to investigate necromancers. (7th level)
2) All the PCs were in the same brutal labor camp, and then shipwrecked together on the way to a mysterious island. (1st level)
3) A mercenary group that had already been working together for a year, starting on a new contract to find a lost magic item in a dungeon. (8th level)
4) 20 years ago, the PCs saved the kingdom from an elemental invasion. After a peaceful retirement, the king has begged them to return to service to stop a new threat. (10th level)