File size reduction in Linux?

[mike Enriquez]

I have a problem. I need to reduce my video files to from 40MB to about 
5-10 MB. My service provider says my files are too large and blocks them.
So I wonder if anyone has had this problem. I need to find a file 
extension that will allow me to reduce these files. Or find a service 
provider that
let me send larger files.
Has anyone in the Linux community encounter this before.

Thanks for any input.

Mike Enriquez