Hence "at the very least". I've got no clue whether the online play was any good, since we never tried it. Probably would have used some client like GameSpy or whatever and that would have been decent and the standard.
Online at the time was handled by Gamespy indeed. This was the reason why many good games of the day could never compete, because the online services sucked compared to Bnet. Bnet was so ahead of the curve back then. If I remember correctly, you had to use a third party program to see servers and I can't remember if there was any matchmaking. Bnet was simply press a button and go, plus tracked stats, special icons, unique chat rooms, etc.
Another example was Armies of Exigo, a brilliant game that came out in 2004, and which was killed off by a combination of shit EA marketing (sent off to die against EA's own vastly inferior BFME, but which had a powerful franchise behind it and all the marketing dollars), a very complete demo with multiplayer functionality that perhaps disincentivized people buying the full game, and Gamespy.