Ubuntu Server 18.04 apt-get Fails

I am still unclear on why I experienced this issue, but it seems a missing grub /boot/grub/menu.lst file was causing apt / dpkg updates to fail. So I created an empty file.

sudo touch /boot/grub/menu.lst
sudo update-grub2

All good. Then proceed with updating the system:

sudo apt update
sudo apt upgrade
sudo apt autoremove --purge

Along the way, there will be a warning that the current menu.lst file is different than the package maintainer's version. Select the option to install the package maintainer's version, and then the rest of the update and cleanup completes successfully. Will see how the next kernel upgrade goes, but problem is solved for now.

Thank you to all who contributed suggestions and help!

I know this should be a comment but I don't have enough reputation.
But I want to let you know I had a similar problem yesterday.
If this answer doesn't work for you, you can contact @videonauth . He's the super nice guy who helped me with this issue.
I will copypaste from his answer the part that will hopefully help you:

First remove the removable packages after having run an update to get the proper package archives updated:

sudo apt update
sudo apt autoremove --purge

This should remove all removable packages so far except the one which managed to get messed up which we can then remove then by installing it and then removing it properly:

cd /var/cache/apt/archives
sudo dpkg -i linux-modules-4.15.0-22-generic_4.15.0-22.24_amd64.deb
sudo dpkg -r linux-modules-4.15.0-22-generic_4.15.0-22.24_amd64.deb  

(Note from Oussema: ^This command was used based on the fact that my system's architecture is amd64. You can see yours using the command uname -a
"i386", "i486", "i586" and "i686" and "athlon" all mean 32 bit. "x86_64" means 64 bit (Opteron or Athlon-64). "i686-64" means 32-bit operation with 64-bit address space (Intel 686 with the new memory mechanism). )

Now cleaning up the archives by running:

sudo apt clean

And now we can reinstall the packages properly after having run an complete update process:

sudo apt update
sudo apt dist-upgrade

with the following line:

sudo apt install --reinstall linux-generic