At my table, instead of characters meeting in a bar, we use Conversation Café. It's a method of discussion which encourages deeper character descriptions and leads to each of the players having a better understanding not just of the other characters and their place in the party dynamic, but often their own as well. It's been effective with new players and experienced ones, and serves as a kind of round robin fireside chat.
We begin by going around the circle and having each person talk in turn, focusing on four questions. Who their character is, why they're with the party, what resources they bring to the table, and what they hope to get out of their association with the party. It can take a bit of getting used to in the first round, but I like to encourage everyone else to focus on listening actively, they'll get a chance to ask questions in the third round. We go around the circle twice, which gives people a chance to think about and flesh out their answers as others speak. Then, entering the third round, players are encouraged to ask questions about the other characters, which can serve not just as a way of learning more about them, but also of creating an opportunity for the other player to think about their character in a way they might not have before.
I don't use this in lieu of character backgrounds, but instead as an introductory tool. However, people will add background elements as this goes on, often with the cooperation of other players, and I've developed a simple idea surrounding Conversation Café in gaming. Everything the players say is true, within reason. If they talk about a bar that wasn't there before, or even an organization, it exists, and I do my best to work with them to make it true. I find that it gives them more freedom with their descriptions, because they don't have to necessarily constrained by the setting, but it also allows me to see more about the kind of game that they want, and the kinds of things they want to be included. I say true within reason because there are some things which, if true, actually make the game less fun. For example, "My character is king of the world" isn't doing anybody any favours if it's true.
I find Conversation Café really useful for a lot of reasons, the first of which being that it lets players introduce their characters on their own terms, so that people know what the player wants them to know, without having to infer it from a chance meeting. Having a discussion about what they bring to the table let's players demonstrate what they want their characters to be relied upon for, essentially setting a standard and managing the party's expectations. It also improves group cohesion, because they own their reasons for getting together, rather than being forced or contrived into becoming an unlikely band of heroes (or villains, etc). It also doesn't take very long, and lets you get straight to the adventure rather than having to finagle the party together which, as a GM, is always one of my biggest headaches.
For more information about Conversation Café and its other uses, check out www.conversationcafe.org, and if you try it, please let me know how it goes. Either way, what methods does your group use to introduce the characters?