The AVI files sounds like a DivX format to me, since you can only compress to get an extra 4 megs out of a 700+ meg file. If you have the orignal source, then recompress it at a lower bitrate. Otherwise you are out of luck, unless you are willing to give up on some loss of quality from the recompressing from a lossy codec.
Typical normal AVI files are quite compressible, and can be compressed to about 2/3 of its normal size.
About the 720MB? Are you refering 1MB as in 10^6 or 2^20? Because a 80 minute CD can hold 700MB if 1MB is 2^20, or about 737MB if 1MB is 10^6.