Ich kenne drei Programme, mit denen ich unter Linux Videos in das mpeg4-Format umwandeln kann: Mencoder, Transcode und Avidemux.
Dabei nutze ich Avidemux eigentlich immer, um mithilfe seiner grafischen Oberfläche die Pixelmaße für Skalierung und abzuschneidende schwarze Ränder zu bestimmen und dann die passende Bitrate zur gewünschten Dateigrösse auszurechnen.