the idea behind MP-first design is to have a working build asap and regularly play it to catch balance issues and unfun features. such approach will actually help design an AI too.
his most noticable mistake?
by that logic, the cutthoart player-like civ5's AI must have been on the right path.
Civ V AI was closer on the right path than IV's. The AI is, according to the game's rules, treated as another player with identical win conditions. They're given some cheats/bonuses so the player has to try in order to win, but that's their design role. That is different from say a megaman boss or a random enemy soldier in Call of Duty. Those have AIs too, but they are not representing the same thing as the player...they're not set as a competitor with identical in-game goals.
If you want a "MP first" game, this is an important step, because the design for the rest of the game influences it and vice versa. Sure, you can toss in solid network code and let people connect, but to have MP actually play well from a strategy standpoint requires some design integration (imbalanced starts, generic tech path, wildly variant civ quality, mechanics that take a lot of time to use all have different standards and potential extra pitfalls).
As for "most noticeable mistake", I meant from a design perspective. Despite that Civ IV's UI is better than V's (measured by #inputs to accomplish something/information presented + #inputs to access), it was the most noticeable due to bugs. But from design it was that some AIs just routinely threw the game, immortal AIs expanding to 3 cities or becoming peaceful vassals without going for culture and giving their overlord technologies etc.
how do you envision this working?
who will host the game?
When Civ IV was released on steam, they dropped support for direct IP connection in-game. This received tremendous negative feedback so they made a "beta" version where you can use it.
To date, Civ IV connecting via direct IP has been the most consistently useful connection method I've used for mainline civ titles, though it's only really useful for playing with people you know (so you can communicate it + password).
Regardless, as CanuckSoldier says it's more a question of not constantly sending superfluous information over the connection; this is not a genre with a big connection burden, nor is it one that is especially damaged by poor latency.