A resposta aceita para essa pergunta mostra uma maneira muito detalhada de minimizar o tamanho do vídeo usando o Mobile Media Converter: Como posso compactar arquivos de vídeo no máximo?
Você também pode usar o Arista Transcoder. O melhor compromisso entre qualidade e tamanho do arquivo deve ser um arquivo mpeg4 com codificação xvid.
O Handbrake também é um aplicativo decente para codificação de vídeo (e excelente para extração de DVD). Um tutorial sobre como minimizar o tamanho do arquivo está aqui no Youtube: link