How can I most easily import Activities and Contacts together?
If it's a new civi installation (with no contacts) it's not bad because all of the external identifiers are available.

I don't know of a way to do them in one fell swoop.

We typically import contacts using their old id as the external identifier and then import the activities.