I’m working on a multiplayer game and I have a server (VPS) from http://www.linode.com/ for ~$17/month. I have yet to see how many players I’ll be able to handle with one server, but I hope the server load will be pretty low. They have west and east coast datacenters in the US, and a datacenter in London, so for ~$54/month you could cover a pretty good portion of the world. In addition, you could provide the server software for users to host (ala Minecraft, Urban Terror, FPSes, etc).
The big difference between losing to real people and losing to AI is that the former is fair. They beat you from experience, skill, practice, etc. IMO, it doesn’t mean much if an AI beats me. However, I do think AI is suitable for some games, and is good to introduce beginners to a multiplayer game before they mauled online.
There are lots of moving parts for a networked game, and that can be interesting and challenging in itself. As you said, that isn’t game design, but it does enable new kinds of game design. It can give more meaning to hard to acquire items. It allows for intra-game social aspects like an economy, trading, marketplace, etc as well as extra-game social aspects like Facebook, GPS, etc. Multiplayer also means you can leverage teamwork, which can be really amazing as it allows you to play with your friends and to learn and grow together. Possibly the biggest reason to go multiplayer is that it can be a HUGE multiplier on replay value. I’ve played Street Fighter IV more than 1000 hours because the online play is fantastic. I would have never played so much against the AI.