Video file size is dependent on the (bitrate X length) of the video and WMV is one of the best at producing small video files and maintaining quality. For example here's a video encoded using a custom profile that is only 70kbps, you can almost stream it with 56k dial up:
http://www.40lbhead.com/headfiles/album ... ndt_du.wmv
You may notice that it's a little choppy. The choppiness is because the framerate was dropped to 15 which allows for more bitrate per frame. We have choppiness but less macroblocking, pick your poison but I'll take choppiness over unviewable anytime. I'm also using mono audio at 20kbps, WMA is probably the best codec for really low bitrate audio.
Switching to a different codec isn't going help you achieve a smaller file. The real issue is compatability. The codec you select should be based on what you want to achieve. For direct links WMV is hands down winner as it can be viewed by the most people. The only codec more dominant than WMV is MPEG1 but that requires 4X the bitrate (or file size) for comparable quality. For embedding in a page flash using .flv or silverlight using .wmv.
For more options encoding to WMV you can download Windows Media Encoder for free from MS's site.
“Results! Why, man, I have gotten a lot of results! I have found several thousand things that won’t work.”
Attributed - Thomas Edison