Compile your own FFmpeg
There are some great audio codecs for FFmpeg which are open source but not completely compatible with GPL, thus they are not included in the FFmpeg package that you can install from the official repositories.
If you want these codecs, you must compile your own FFmpeg.
Here you can find a nice description of the available audio codecs. Which one should you use? In short, they come in this order:
libfaac > Native FFmpeg AAC ≥
libfdk_aac provides the best quality.
You can download static builds from here but they don’t include
libfaac either :(
Fortunately, compiling FFmpeg under Ubuntu is quite easy. You just need to follow this guide.
I have an installer script for Ubuntu called jabbatron. The new version of this script includes (1) compiling FFmpeg, and (2) updating FFmpeg. They are available under the menu point “(170) install from source (mc, tesseract3, ffmpeg)…”. This script automates all the steps that are described in the aforementioned guide.