VCD quality MPG is about 10MB/minute.
Converting to WMV will make it smaller for the same quality and the tool is free from Microsoft.
http://www.microsoft.com/windows/windowsmedia/9series/encoder/default.aspx
Converting to RM will also make it smaller, but you said no spyware / adware so stay away from Real.

Converting to MOV will make it so it plays better on Macs than PCs. They wouldn't do the same for you.