1. Story arcs and badge missions can be done later via Ouroborous Flashbacks, so you're good there. You'll miss out on some random missions, but off the top of my head I can't think of anything that is a big deal in that regard.
2. As you do missions for a contact they will eventually introduce you to another one, so you'll meet a good chunk of them that way if you don't outlevel that specific contact. For arcs related to zones, you can usually just go to the first contact in the string without being introduced. For example, once you hit level 20(I think) you can go to Stephanie Pebbles in Striga Isle and start her missions. After you do all four arcs in that zone you will be introduced to Ernesto Hess who is a Task Force contact. In order to start that specific Task Force you do have to be introduced to him. There may be a list of such things somewhere, but I'm not sure.
3. I don't think there are any game spanning arcs like that, but I'm not sure.
4. If you both have the same mission, non leaders will have the opportunity to complete theirs when your mission is completed.