Todo o crédito para @heemayl para os ponteiros que resultaram nessa resposta. Aceitei essa resposta, mas aqui estão os detalhes de como corrigi-la, caso isso seja útil para os outros.
O problema foi causado por uma tabela full inode. Pelo que entendi, existem duas partes para um sistema de arquivos, inodes e espaço. inodes estão relacionados ao número de arquivos, onde o espaço é o tamanho que eles têm. Meu sistema estava repleto de milhões de arquivos minúsculos causados pelo Ubuntu não remover os kernels antigos. Como o sistema funcionou por um longo tempo, eu tinha mais de 40 kernels, incl. arquivos de cabeçalho, instalados, o que é muito para um sistema de arquivos da partição do sistema de 20Gb.
Isso significava que o dpkg não podia concluir uma instalação - precisava de mais espaço para concluir seu trabalho - mas, infelizmente, isso não significava que eu poderia criar espaço usando o apt para desinstalar coisas!
A solução que encontrei foi mover todos os arquivos /usr/src/ para minha outra partição, deixando apenas um link simbólico para os arquivos no fs completo:
sudo mv /usr/src /home/usr-src
sudo ln -s /home/usr-src /usr/src
Depois de fazer isso, pude deixar o apt completar:
sudo apt install -f
E depois disso eu consegui desinstalar todos os kernels mais antigos que eu não precisava, liberando espaço, e então eu pude mover a pasta src de volta.