Então, depois de mais pesquisas e de ler cuidadosamente as mensagens de erro, parece que dpkg
precisou ser reinstalado.
sudo apt-get install --reinstall dpkg
O que deu a entender que esse era o problema (se alguém pesquisar e vir isso) é que update-alternatives: not found
estava na mensagem de erro. Assim que o dpkg foi reinstalado, os outros pacotes passaram a ser instalados normalmente de forma automática.