The visual jerkiness is based around the game simulation running too slowly -- the fact that backgrounds and such are still scrolling smoothly is a very good indicator that it's not your CPU or GPU that are the limiting factor, since it's still drawing as fast as it can but the game itself is unable to proceed.
Normally that could be an indicator that someone else is the problem and your game is just having to wait to catch up (that's why the other players' ships are jerky), but in this case since the wait message is appearing next to your name on the host's machine, that means that the problem is that everyone else is waiting on you.
Given that changing the performance profiles didn't affect anything, that just confirms what I said above, that the problem isn't with your CPU or GPU. That's why changing the affinity also didn't do anything, because actually your CPU is probably idle quite a bit at the moment while all that jerkiness is going on.
The actual problem, by process of elimination, is therefore a networking issue. That's also consistent with the fact that you're playing full speed in single player, where there's no networking involved. Given that, what you'll want to do is run through the steps outlined under "Dealing with a network bottleneck" here:
http://www.arcengames.com/forums/index.php/topic,74.0.htmlAt worst, you should be able to increase the network skip to the point that the game becomes playable. Ideally, if there is an updated LAN driver you can get for your computer, or if lowering the MTU setting helps, or if you are on an unreliable wireless network connection that you can get off of, or if there are a bunch of background uploads/downloads on your computer or your network that you can stop... (whew, long sentence). Anyway, one of those ought to do the trick.
Hope that helps! And if there are further questions, obviously feel free.