А что говорит apt с PkgProblemResolver?

apt-get -o Debug::pkgProblemResolver=yes remove firefox-esr
Чтение списков пакетов... Завершено
Построение дерева зависимостей... Завершено
Starting
Starting 2
Investigating i586-wine-vanilla.32bit
Package i586-wine-vanilla.32bit has broken dep on webclient
  Considering rekonq 0 as a solution to i586-wine-vanilla.32bit 0
  Removing i586-wine-vanilla.32bit rather than change webclient
Investigating firefox-esr-ru
Package firefox-esr-ru has broken dep on firefox-esr
  Considering firefox-esr 10002 as a solution to firefox-esr-ru 0
  Removing firefox-esr-ru rather than change firefox-esr
Investigating firefox-esr-uk
Package firefox-esr-uk has broken dep on firefox-esr
  Considering firefox-esr 10002 as a solution to firefox-esr-uk 0
  Removing firefox-esr-uk rather than change firefox-esr
Investigating firefox-pepperflash
Package firefox-pepperflash has broken dep on /usr/bin/firefox
  Considering firefox-gost 0 as a solution to firefox-pepperflash 0
  Removing firefox-pepperflash rather than change /usr/bin/firefox
Investigating kde5-small
Package kde5-small has broken dep on webclient
  Considering rekonq 0 as a solution to kde5-small 0
  Removing kde5-small rather than change webclient
Investigating kde5
Package kde5 has broken dep on .p8.216466.100.1.1-kde5-small-18.04.3-alt2
  Considering kde5-small 0 as a solution to kde5 0
  Removing kde5 rather than change .p8.216466.100.1.1-kde5-small-18.04.3-alt2
Investigating kde5-big
Package kde5-big has broken dep on .p8.216466.100.1.1-kde5-18.04.3-alt2
  Considering kde5 0 as a solution to kde5-big 0
  Removing kde5-big rather than change .p8.216466.100.1.1-kde5-18.04.3-alt2
Done
Следующие пакеты будут УДАЛЕНЫ:
  firefox-esr firefox-esr-ru firefox-esr-uk firefox-pepperflash i586-wine-vanilla.32bit kde5 kde5-big kde5-small
0 будет обновлено, 0 новых установлено, 8 пакетов будет удалено и 0 не будет обновлено.
Необходимо получить 0B архивов.
После распаковки будет освобождено 189MB дискового пространства.

Установите любой другой браузер, который предоставляет webclient.

Ааа, ну да. Просто apt с какого-то времени стал так себя вести. Не стремится устанавливать пакеты на замену.
Если `apt-get install webclient` любой из неустановленных, то потом firefox-esr без проблем удалится.

А вообще
"Removing kde5-small rather than change webclient"
выглядит бессмысленно, т.к. "webclient" после этого не только "change", а вообще "removing".

Т.е. он там по логу всё порывается rekonq поставить, но "ни шмагла".

Мне кажется, поведение apt не изменилось. Может быть, задачу нужно поднять на Сизиф?

Продукт более не поддерживается. Если актуально, то необходимо перевешать на новый поддерживаемый репозиторий (p10, p11, Sisyphus).