Compressing it usually doesn't work because it's already compressed inside the AVI file. You might make it slightly smaller occasionally with a very aggressive compressor, but don't count on much.
I think it's larger than the limit because of the way files are transferred by e-mail. Whenever files are transferred by e-mail, they're converted into text characters (encoding, e.g. MIME). This increases their file size by about 30-50%. If I understand what you're seeing correctly, this is true of all e-mail based file transfers.
The easiest thing is to use some kind of file drop-box site... rapidshare, dropbox, etc ... instead of sending it via e-mail.