You need to use a codec with a high compression rate such as MPEG4. There's two popular "non-microsoft" MPEG4 codecs available in the form of DivX and Xvid. These are great codecs which, combined with low resolutions, will get your video down to 16MB file size. I use VirtualDub to encode using these codecs; you can find a guide to VirtualDub on my site and a a google search will get you the codecs themselves.
Although these codecs work wonders, the end user will have to download and install them if they don't already have them. One idea is to Zip up the videos with the ffdshow filters which will allow playback, but it involves the end user actually doing something
Another alternative is to encode to WMV. You can do this with Windows Media Encoder (a free download from the MS site). If you encode using WMV8, the video will be playable on just about any windows box out there. In an ideal world, I'd use Xvid, but alas not everyone had the necesary codecs, so I tend to use WMV for downloadaable clips.
Theres a guide to windows media encoder on my website.