[Bear in mind I know very little about codecs, so this could be way off; most of it is based on inferences from what I've read here.]
There are basically three audiences to worry about, Windows, Mac, and Dial-Up. It seems like the general consensus is to ignore Dial-Up, so that leaves us with Windows and Mac users.
On the Windows side, it seems like the basic choices presented thus far are MPEG, WMV and XVID. MPEG, as I understand it, is pretty universally playable, but doesn't offer the best compression. WMV is a nice middle ground. And XVID has the best compression but the least ubiquity.
In the Mac camp, we've got MPEG and Quicktime. From what I've read here, it seems like quicktime looks like a pile of flaming ass unless you ramp up the filesize.
So it would seem that the best choice would be to offer a choice of either WMV or MPEG, with perhaps the option of a high-res XVID copy if you've got the extra space/bandwidth.
Keep in mind that the goal, in the end, should be universal playability with decent quality, rather than absolute best-quality that only some people can play.