Solución fácil, pero uno por uno

Si no te importa ir archivo por archivo, lo más sencillo es usar Transmageddon, una aplicación que viene empaquetada en casi todas las distribuciones Linux, y que resulta muy fácil de utilizar.

Solución difícil, pero todos de una vez

Usaremos directamente GStreamer 1.0, que es la herramienta que usan entre bastidores casi todas las herramientas gr√°ficas de audio en GNOME.

Crea un script llamado ~/.local/bin/gst-video-compress con este contenido:

#!/bin/bash

# Transform to Ogg (VP8 + Opus)
function transcode {
    gst-launch-1.0 \
        filesrc "location=$(readlink -f $1)" ! \
        decodebin name=demux ! \
            queue ! \
                progressreport "name=Encoding video for $1" ! \
                vp8enc ! \
                oggmux name=mux ! \
                filesink "location=$(readlink -f ${1%.*}).ogg" \
            demux. ! queue ! \
                progressreport "name=Encoding audio for $1" ! \
                audioconvert ! \
                audioresample ! \
                opusenc ! \
        mux. \
    && [ "$RM" == "y" ] && rm "$n"
}

# Fork it to make use of all processors
for f in $*; do
    while [ $(jobs | wc -l) -ge $(nproc) ]; do
        sleep 5
    done

    transcode $f &
done

# Don't exit until everything is finished
for j in $(jobs -p); do
    wait $j
done

Esto coge cualquier vídeo y lo transforma a Ogg (VP8 + Opus) con el mismo nombre de fichero que el anterior, y además transcodifica simultáneamente tantos videos como procesadores tengas. Si quieres entender lo que hace, consulta la explicación que ya di sobre qué son las tuberías de GStreamer y esta respuesta de Stack Overflow. También puedes usar el comando gst-inspect-1.0 con cada plugin (filesrc, decodebin, queue, etc.) para ver qué hace cada cual.

Ahora puedes invocar ese script de la siguiente manera:

$ gst-video-compress *.mp4 *.mov

Y si quieres que autom√°ticamente vaya borrando los ficheros conforme vaya transcodific√°ndolos sin errores:

$ RM=y gst-video-compress *.mp4 *.mov