try looking around through this list:
http://www.downseek.com/directory/65.asp
Some are freeware some are shareware, but there's gotta be one that does the job. I usually use TMPEG ENC Xpress which is the version of TMPEG ENC that costs money, I don't know if the freeware version features the same range of conversions, but you may want to try there first.
If that fails, one way to get videos small enough to stream or have a reallly small download time, is to use DivX. It sucks the quality out of the video kind of, but it can take a 600 meg avi and turn it into a 10 meg file. Dr. DivX would be the tool to use in that case. The demo lasts for 15 or 16 days or something, so again I got the full version.
Hope ya find somethin...