Как оптимизировать видео для веба (из под линукс или через интернет-сервис)?
FFMPEG поможет вам. Любые манипуляции с видео+аудио. Любые доступные кодеки.
С первой страницы гугла:ffmpeg -i inputfile.avi -codec:v libx264 -profile:v baseline -preset slow -b:v 250k -maxrate 250k -bufsize 500k -vf scale=-1:360 -threads 0 -codec:a libfdk_aac -b:a 96k output.mp4
Конвертирование видео в 360p at 250kbit/s
В VLC можно конвертировать в любой формат. А вот в какой лучше - вопрос уже. FLV может, а может и MP4.