Troll in the Corner has a post with five ideas for how to avoid the old cliché of the party meeting up in a tavern for their first adventure.
What's fascinating about all of these is the assumption that the party meets for the first time right as they take up the call to adventure. This assumption so ingrained in D&D culture that it's taken for granted - and yet, narratively, it's so awkward that it practically begs for cliché. With all these people meeting for the first time, a meeting place of strangers is an obvious choice.
So why is this type of start so common? It's baked into the rules of D&D, that's why! Not explicitly, of course, but here's what I mean:
1. D&D encourages individual character-making
To break away from the cliché, you need to have a party premise. The entourage, say, of a wealthy Venetian merchant having a mid-life crisis decides he's going to hire a group of mercenaries to raid Alexandria for the relics of St. Mark and bring them back to Venice. He goes along as expedition captain, leading a mix of fresh recruits and seasoned veterans of wars with Genoa.
But D&D markets adventurer career paths directly to players. Players invest emotionally in working their way up to Duellist or Underdark Assassin long before a particular adventure has been minted, and they're able to do so even if this makes no sense whatsoever in the context of the adventure.
Perhaps it's a maritime campaign in a sea monster-haunted archipelago. You might expect the adventurers to become tanned, salt-stained sailors - but nope! As long as you collect your XP, you can advance along your wish fulfillment career path, utterly untarnished by your actual experiences.
This kind of zero-cooperation concept building is a powerful tool for hooking casual players, or players not really mature enough (or simply not interested in) collaborating creatively. "I'll follow the plot, but keep your hands off my character!"
Of course you can have a party concept, but this runs subtly against the grain; players will need to give up tantalizing options in order to make it happen.
2. D&D encourages niche coverage
With D&D's niche protection, playing a party built around everyone being a mercenary fighter is a sure-fire way of getting your asses handed to you, just as surely as a whole party made of clerics. Parties that cover off all the combat roles are harder to explain, and are self-consciously meta-game tropes. "We need a tank."
Of course you can have a themed party that's missing certain niche roles by design, but this runs against the grain - the DM has to be very mindful of the impact of certain types of encounter, like invisible creatures or a wave of undead, that will be devastating for a party not designed to handle them.
3. The Weirdness of Levels
D&D's nearly linear power advancement makes a wide mix of adventuring levels problematic. Fifth-level fighters are vastly more effective than first-level fighters, so much so that encounters which barely challenge the veterans can be extremely risky for the greener soldiers, who have little to contribute besides serving as a distraction.
This puts tremendous pressure on the party to start out at the same or similar experience levels. Our hypothetical Venetian party, with its wealthy non-combatant leading a group of fifth and second-level fighters, is decidedly unstable in D&D.
Of course, you can do this if the DM is clever enough always to challenge the party appropriately, with mixed-level encounters - or by disengaging from the mechanics to one degree or other (e.g. not using the battle mat for combat, for example). But this takes effort and skill.
4. Missing Social Conflict
Why are the mercenaries following the merchant at all? In D&D, the only meaningful force that constrains players is the threat of injury. Social pressures, particularly between player characters, are non-existent.
Unarmed in this area, the expedition leader is irrelevant. Other than a few gold coins, at a game mechanical level he has nothing meaningful to contribute whatsoever. Who would want to play this character?
Of course, you can play out stories like this in D&D, it's just that they happen without any mechanical support. This can be satisfying, though for a story that focuses on social conflict, mechanics are interesting for the same reasons that combat mechanics are fun.
But free-form social conflict (over, say, the leadership of the party, or the choice of strategy the party takes) carries a few important risks. With no mechanical reason to back down from an argument, in-character argument either escalates to in-character disruption (PC-on-PC violence, or someone storming out of the party) or gets resolved at the player level.
A very collaborative group, all on the same page, may be able to role-play the debate amicably, with one player choosing to have his character 'be convinced'. More often than not, however, the debate rages on interminably, someone gives in reluctantly because of player-level tension: the winning player being more stubborn, persuasive, intimidating, or enjoys a more of the group's support.
D&D invites players to make a "balanced party" out of thematically unrelated character concepts, all of the same experience level, without meaningful intra-party tension. The leaderless, informally egalitarian troupe of murderhobos is a natural consequence!