Кодеки в большинстве случаев везде одинаковые и поставляются от 
libav, они есть из коробки в большинстве дистрибутивов. Для ubuntu есть еще пакет 
ubuntu-restricted-extras, в нём расширенная поддержка кодеков, возможно нечто такое есть и для других дистрибутивов.
В самом vlc изначально есть много своих кодеков и он из коробки жрет почти всё, но если вдруг не справляется - можете попробовать 
mpv.