Какой формат видео-файла наименьше всего по размеру?

Зависит не только от формата, но и от того, как ужмёшь.
Я ужимал видео просто в формат AVI DivX так, что 1 минута видео занимала всего 1,1 М - на обычный CD влезло бы свыше 10 часов такого видео! И смотреть было всё-таки еще возможно - убедитесь сами:

При такой степени компрессии пришлось принимать меры еще и к максимально-возможной компрессии звукового сопровождения: размер видеоданных уменьшился настолько, что стал сравним с размером фонограммы. Так что существенно более высокая компрессия, по-видимому, невозможна в принципе.
В остальном же - озаботьтесь тем, как Вы (или тот, кому Вы перешлете этот файл по почте) будете его воспроизводить. Если на аппаратном устройстве - то какие форматы оно поддерживает. Если на компе - то сколь экзотичен кодек. Я ужимал весьма общеупотребительным кодеком DivX 3.11.

Это нужно выбирать из тех, что поддерживает телефон или .. ну, куда он загружаться будет....

Дело в том, что разные кодеки по разному сжимают РАЗНЫЕ сцены. То есть один кодек хорошо сжимает статичные сцены, с малым количеством движений; а другой - хорошо сжимает динамичные сцены. Поэтому, в зависимости от динамики фильма, его сцен, также зависит конечный объем после сжатия. Определяется экспериментально УВЫ!
Наиболее распространены DiVX, XVid. Из последних, - flv-файлы (не помню марку их кодека)

точно! это вам не фиги воробьям показывать) ) сам как-то мучился, там столько настроек! ууу