Software index is broken

Question

I keep getting a prompt after I have upgraded from Ubuntu 18.04 to 20.04 that my Software index is broken and should run Sudo apt-install -f but if I run this I get:

Building dependency tree       
Reading state information... Done
The following packages were automatically installed and are no longer required:
  linux-headers-4.15.0-76 linux-headers-4.15.0-76-generic
  linux-image-4.15.0-76-generic linux-modules-4.15.0-76-generic
  linux-modules-extra-4.15.0-76-generic
Use 'sudo apt autoremove' to remove them.
The following packages will be REMOVED:
  linux-image-4.15.0-74-generic
0 upgraded, 0 newly installed, 1 to remove and 8 not upgraded.
2 not fully installed or removed.
After this operation, 8,398 kB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 628194 files and directories currently installed.)
Removing linux-image-4.15.0-74-generic (4.15.0-74.84) ...
/etc/kernel/postrm.d/initramfs-tools:
update-initramfs: Deleting /boot/initrd.img-4.15.0-74-generic
/etc/kernel/postrm.d/zz-update-grub:
Sourcing file `/etc/default/grub'
Sourcing file `/etc/default/grub.d/init-select.cfg'
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-5.4.0-51-generic
Found initrd image: /boot/initrd.img-5.4.0-51-generic
Found linux image: /boot/vmlinuz-5.4.0-48-generic
Found initrd image: /boot/initrd.img-5.4.0-48-generic
Found linux image: /boot/vmlinuz-4.15.0-76-generic
Found initrd image: /boot/initrd.img-4.15.0-76-generic
/etc/grub.d/bin/grubcfg_proxy: error while loading shared libraries: libcrypto.
so.1.0.0: cannot open shared object file: No such file or directory
run-parts: /etc/kernel/postrm.d/zz-update-grub exited with return code 127
dpkg: error processing package linux-image-4.15.0-74-generic (--remove):
 installed linux-image-4.15.0-74-generic package post-removal script subprocess
 returned error exit status 1
dpkg: too many errors, stopping
Errors were encountered while processing:
 linux-image-4.15.0-74-generic
Processing was halted because there were too many errors.
E: Sub-process /usr/bin/dpkg returned an error code (1)

This is what generally happens. I get a prompt:

If I click on continue, I get software index is broken

and if I click on partial upgrade, it starts upgrading but then

and

then I get these two and the partial upgrade is done but the prompt that came first pops again after few hours.