Do you want to stream or download the video?
Do you want generic easy access to the file (standard codec, crappy
Or would you rather use a good codec (needs tech savvy or alternative media player to see)?
Flash video is not too bad given the size. WMV is fine but I'm not sure it works on Macs. Quicktime MPEG4 has a pretty good quality and the player is quite widespread. I suppose I don't need to say avoid realmedia like the plague. Simplest codec to use for download would be MPEG1 (but then you get a crappy quality).
Other than that, doom9.net has a lot of info on codecs and video, if you want to look for more efficient solutions, take a look.
Personally, I would rather have people download videos using one of the latest DivX codecs, or I would go with Flash.
[download a life]