I usually try to split the difference, by both establishing a relationship between characters (often A&B and C&D separately, like was suggested above) ahead of time, and then go with the 'in media res' approach -- but rarely with combat. Last couple games' beginning:

-One PC was a professor of alchemy and had prepared a minute of a (hilariously weird) lecture, which he started delivering, only to be interrupted with a student's eyes going all white and blazing, then the teleporting in of two bizarre artificers (one tattooed all over, with chainmail and earrings and using a lead pipe for a wand, one dressed in bright peacock blue parachute pants, with goggles and a giant clock around his neck, like the love-child of Flava Flav and Princess Jasmine), who chase him away.

-PCs wake up in a serene Dragonborn monastery in the mountains, with no memory of how they got there and no equipment, and nobody quite willing to answer their questions...

Set up an interesting environment and interesting characters, and players get sucked right in without all the "okay, so i introduce myself, say what mystic item I'm searching for, declare my oath against the necromancer, etc"...