First, about the GPT error that you are seeing, notice the text that says:
Caution: invalid main GPT header, but valid backup; regenerating main header
from backup!
This is an indication of the fact that gdisk starts with the assumption that your disk probably has a GPT table (unlike fdisk and other older utils which first look for an MBR type table).
When you run gdisk on the 110G drive, it's not finding the main GPT table at the beginning of the drive (because that has been replaced with the 16.04 MBR table), but it is finding the old no-longer-used backup table at the end of the drive.
If you post a Gparted screen capture of your current 110G drive partitioning, we can look at how to fix this manually by zeroing out this table with a special dd command using the skip= option, to skip over the 16.04 O.S. and delete the unwanted GPT backup table.
You may want to do this in conjunction with resizing your 16.04 working partition back to the max size possible, let me know, it's not that difficult.
Now moving on to the strange grub boot loader behavior . . .
If you boot up into your old 16.04 installation and from your 16.04 mate terminal run:
sudo update-grub
... it should see the 110GB drive as sda, and the update-grub should fix your older 16.04 grub boot loader so that it will drop the now-nonexistent 12.04 entry, and correctly show both the 18.04 and 16.04 boot options (although the order may be reversed -- 16.04 first, 18.04 second )
The issue of your system sometimes booting from the wrong grub is a little strange, because which boot loader loads should purely depend on the boot drive order specified in your BIOS.
What could be potentially happening is that for some reason your 220GB drive is a little slow to spin up, and sometimes the system moves on to boot from the other drive, and so loads the other grub..
You might be able to fix that by removing the 110GB drive from the boot device list in your BIOS so the system will be forced to wait for the 220GB drive and boot from that.
With MBR partitions we are booting in legacy non-UEFI mode, and sometimes your PC BIOS will also have some additional setting related to "legacy compatibility" for the SATA ports that might help.