Entonces lo que quieres es bajar el tamaño, lo de la calidad casi que va incluido... te recomiendo codificar en xvid con un bitrate de 1100 y tendras una calidad "decente", podras reproducirlo en la mayor parte de aparatos.
Ahora bien si quieres mas calidad codifica en h264 y casi no notaras diferencias del original. Como programas hay muchos, gratis...
http://www.mediacoderhq.com/ es un poco complejo, pero cuando lo entiendes un poco, es sencillo, con cola de trabajo...