This may already have been hatched out since said video, but here is what I was thinking. To accommodate the crossing story paths. what you could do is based on the path one is on they would get a mission that requires them to team with a certain character type.

From there I figure there are a few ways you could go:

1) make it such that each time you are asked to team up with that type again if you team with the same person you get a bonus or points toward a bonus (unlocked costume piece or a power you can only use teamed up in a duo or w/e)

2) the second idea I call "taking up the cause." this would be some something fun for friends and SG mates, but could be done with that random person. After completing the mission you can choose to start a whole story arch (maybe 4-10+ missions) which can ONLY be completed with that person or group of people who were in the group with you AND chose to also "take up the cause" with a pay off at the end. these arcs could be self adjusting based on party size and level. So, if 6 of you accept out of 8, but then half way through only 4 show up (maybe cause they switched sides or w/e), or you took it at lvl 25 and get to level 40 before the end it can still be completed. you could even do larger ones where in for Large groups like of 8 people you get say 20 total missions, but not all of them are 8 man, sometimes during you might get four missions at once that require two people or 8 solo missions (maybe with suggestions of archetypes that should take each), the catch here being that the arch doesn't advance till each mission is done (again mission numbers in this case would adjust if people dropped the cause) and people who complete one of the missions in this part of the arch can't complete the other. In other words if captain obvious and general frustration do the mission to capture Whiney-pants McGee, then neither can be involved in the mission to stop the night bomber from bombing in the night.