ffmpeg - бесплатно, но работает через командную строку. Есть под Windows и под Linux.
Пример перекодирования видео из 720 в 480:
ffmpeg -i input.mp4 -vf scale=720:480 output.mp4
размер файла уменьшился с 55 Мб до 14 Мб.
Через параметры командной строки можно задавать что угодно: формат, битрейт, разрешение, можно обрезать по времени и т.п. Примеры командной строки для разных действий можно нагуглить.