Did my regular Ubuntu install with a 1 MB unformatted partition at the beginning of the hard drive with a GPT partition table. The 1 MB partition should have the flag bios_grub.
After the regular install, I ran
grub-install --target=i386-pc /dev/vda
Then I boot up in both secure UEFI mode and a legacy boot using the MBR format.