En Somos Libres, uno de los mejores blogs de software libre en español que he encontrado últimamente, ofrecen una comparativa de conversores de video bastante interesante.
Recuerdo que Transmaggedon me encantó, pero no lograba recordar cómo se llamaba el programa. Hasta entonces usaba OggConvert, que también va de categoría, pero sólo transforma a formatos libres (ogg, mkv y webm), y a veces necesitamos transormar a otro privativo.
Respecto a conversores de audio, me quedo con SoundConverter, que funciona de maravilla y permite transformar montones de archivos a la vez. Tampoco tiene mala pinta el Gnac, pero no lo he probado.
Todas estas son aplicaciones de escritorio basadas en GTK y GStreamer. Para aplicaciones por consola, consulta este estupendo artículo.
