Vou postar os comandos que funcionaram para mim, na ordem:
sudo dpkg --purge --force-depends texlive-lang-other texlive-latex-extra tex-common texlive-fonts-recommended texlive-pictures texlive-metapost
sudo apt-get install -f texlive-lang-other texlive-latex-extra tex-common texlive-fonts-recommended texlive-pictures texlive-metapost
sudo mktexlsr
sudo updmap-sys
Dependendo de quais arquivos * .map estão gerando os erros, talvez seja necessário limpar diferentes pacotes. Procurei on-line por cada erro * .map de qual pacote estava, depois purgou-o, reinstalei-o e mktexlsr
e updmap-sys
. Eventualmente, não houve mais erros.