I would prefer a non online multi player, so that you only play fiends via IP - IP. That way balancing issues can be ignored, and the length of the game would not be such an issue, and the waiting time between turn not such an ussue. It would mean a text chat section be added to the game 

These would ensure that the single player game is not affected in any way, and reduce the amount of work to implement it.

No servers, as te players would host the games themselved etc.

There's only 1 way multiplayer makes sense in a game like this: Head to head only and based on file swapping. It would be like playing long distance chess. I set up a game with a buddy on the other side of the world. Whoever goes first would end his turn and an export file is created. This file is emailed (or whatever) to the friend who imports it, then takes his turn. Wash, rinse, repeat. Actually now that I think about it, that would probably really suck. Nevermind.

SOMETHING just to shut them up. I hope it doesn't interfer with the single player experience because I'll never use multiplayer.