ATUALIZAÇÃO: Eu consertei o problema, revertendo para uma versão mais antiga do libcurl3-gnutls.
Para quem está com o mesmo problema, eu fiz isso listando o cache:
apt-cache showpkg libcurl3-gnutls
O que me deu uma saída longa, mas a parte importante foram as três últimas linhas:
Provides:
7.47.0-1ubuntu2.6 -
7.47.0-1ubuntu2 -
Reverse Provides:
Eu usei o seguinte comando para baixar a versão mais antiga:
sudo apt-get install libcurl3-gnutls=7.47.0-1ubuntu2
Então corri sudo apt install curl
como normal.
Obrigado pela ajuda!