Everyone knows something about another player character and even if they're not the closest of friends have been introduced in the past — which can be decided by the players at the time of meeting or ahead of time if they are creating a back story for their characters.
If you would like your players to come up with a short back story before you meet for your first game, then you can let the players know which other characters they will know ahead of time, then the players can decide on how their characters know each other and why they are adventuring together. This way each character will know at least one other and have a reason to be travelling or meeting together as a group. It's not that every character will know every other character, but each will know at least one other.
You can even have the players introduce their friends as they arrive at their meeting point, decide who arrives first and go from there — a bit like Thorin and his gang arriving in dribs-and-drabs at Bilbo Baggins residence in the Hobbit.
An alternative, which we played in a very memorable Call of Cthulhu campaign was that each player wrote down a paragraph or two about their character that was common knowledge. Characters were well-known in their fields of expertise; the information given could have come from a range of sources that would be publicly available: whether that was in newspaper articles; university lectures given by the character; or just rumours and hearsay regarding the dilettante about town. Whether the information was true, had a nugget of truth or was completely fictional was up to the players to decide.
This can work well with the Everyone Knows Someone theme, where in addition every character knows one other character well — well enough to know a dark secret from their background. In addition to creating their public persona each character created a secret that was given to another player when the game started, how they came to know about these hidden details was again left to the characters to decide. In our game the secrets came out during roleplaying, but this can easily be decided prior to play if you so wish.
This can work very well for some game genres, maybe less so for others, and maybe you'll have to get creative on working on how this public information would have been available to the characters if the setting is of a more historic or fantasy variety. However, in modern games and especially Cyberpunk or sci-fi genres where information could be readily available this can be a really fun way of introducing characters. After all, what goes online stays online, and in some dark dystopian future knowledge is everything.
Circumstances and tragedy can throw the characters together, forming a bond that will last a lifetime (or at least a campaign). I've run these type of introduction scenarios many times over the years, and they can be a great way of introducing the characters to each other through one calamity or another.
Although this does require more work by the Game Master than the suggestions above, and there is little or no player involvement in setting up how their characters know each other (they likely won't know each other at the start of the campaign), but you can get really creative and drive the story forward from it's very inception.
There are no hard and fast rules for coming up with a intriguing opening scenario, indeed you can ask players not to come up with a background for their character until after the first session or scenario — they can then fold in the events into their back story once they know the details. I have, on occasions, given the players an event that occurred prior to the campaign starting that they had to work into their backgrounds.
In a Pathfinder campaign I ran some ten years ago, the players were all given a piece of information that they needed to incorporate into their back story — the information that I gave them was that they witnessed a comet in the night sky on an important day for the character, an omen of the future events that were about to transpire. The comet was witnessed on a specific day, so characters of various backgrounds would all have been different ages, and it was left to the players to decide what they were doing and why this particular day was important for them. They were also asked to incorporate why they found themselves being sold at a slave auction in Kaer Maga, where the adventure started in a rain soaked market place. The auction proceeded at length, where all six characters were bought on mass by a person unseen for an amount far in excess of what would have been considered normal. The very someone who had been following their paths since the first sighting of the comet, and who held intimate knowledge of the prophecy that would change the world. What were their motives and what was the meaning of the comet, they didn't know at the time — indeed they didn't find out about the significance of the comet and the first details of the prophecy until the third scenario, weeks of game time in the future. All the characters were bound together by the prophecy, their sale at the slave market, and discovering the motives of their buyer.