You should first determine whether you want to use a BIOS/CSM/legacy-mode boot or an EFI/UEFI-mode boot. The former is the way that PCs have been booting since the 1980s, but it's an ugly and hackish system that will be going the way of the dodo before too long. Windows ties BIOS-mode booting to the MBR partition table, which you're not using (but could; your disk is nowhere near big enough to require GPT). Linux, FreeBSD, and most other modern OSes are more flexible, and support BIOS-mode booting from GPT; but there are sometimes firmware-created complications, and of course if you later decide to install Windows in a dual-boot setup you'll need to make changes or compromises.

EFI/UEFI-mode booting is less of a hack; but EFI implementations vary greatly in quality and the overall level of expertise and support on the Web for EFI is lower than that for BIOS. Windows ties use of GPT to EFI-mode booting, so if you expect to ever install Windows on your computer, EFI is definitely the way to go. Older computers are BIOS-only. EFI began to take off in the marketplace in mid-2011, so if your computer is older than that, you might not be able to use EFI.

If you go with BIOS-mode booting, you should create a BIOS Boot Partition on the disk. There's enough room at the start of your disk for this partition, but you'll need to set your sector alignment value to 1 (from the usual 2048) for this to work. I don't know offhand if this can be done with parted, but you can do it with gdisk. (Note that the space at the start of your disk is slightly under the recommended 1MiB size for a BIOS Boot Partition, but just by a few sectors. It will probably work fine, but might conceivably fail at some point in the future.) Alternatively, you can shrink any of your partitions by 1-2MiB to make room for the BIOS Boot Partition. This partition does not need to be the first partition on the disk, although that's the conventional location.

If you go with EFI/UEFI-mode booting, you must create an EFI System Partition (ESP). This partition must be FAT-formatted and must be significantly larger than a BIOS Boot Partition, so you'll have to resize something to create it. I recommend a size of 550MiB, although a tenth of that might work in a pinch.

To install GRUB, you should first be sure that you've installed the correct GRUB package. I'm not sure of naming in all distributions, but in Ubuntu, it would be grub-pc for BIOS/CSM/legacy mode and grub-efi-amd64 for EFI/UEFI mode. An EFI-mode installation will also require booting whatever you're using to install GRUB (a live CD/USB, presumably) in EFI mode. Doing this may require using your computer's built-in boot manager, which is typically accessed via a function key, but the details vary from one computer to another.

If you want to use UEFI boot mode, then you're installing the wrong GRUB variant to the wrong place.

UEFI systems do not hold their bootloader directly in the 'MBR' of /dev/sda. They require a special partition, called the "EFI system partition", which holds files that comprise the bootloader. (For example, installing GRUB2 would copy a "grubx64.efi" file to that partition.)

So you must first create that partition, set the correct "partition type" in fdisk, format it with the correct filesystem, and mount it on e.g. /boot/efi.

(The EFI system partition should be ~200 MB, with partition type C12A7328-F81F-11D2-BA4B-00A0C93EC93B on GPT disks, and must be formatted as FAT32 using mkfs.vfat. It can be anywhere on the disk, so just shrink one of your existing partitions to make some space.)

After creating and mounting the partition, tell grub-install to install everything into /boot/efi and do not specify a disk name:

sudo grub-install --target=x86_64-efi --efi-directory=/boot/efi
sudo grub-install --target=x86_64-efi --efi-directory=/boot/efi --removable

More detailed instructions can be found in:

• https://wiki.archlinux.org/index.php/GRUB#UEFI_systems

Note: The error message is shown because grub-install is currently trying to install GRUB2 for BIOS, not for UEFI. This might be because your system has currently been booted in "legacy mode" (e.g. from an UEFI-incompatible .iso image).

If you're in this situation but want the main system to use UEFI, ignore the error messages and just follow the above instructions. You may need to use grub-install with --removable at first, then reboot into your freshly-installed system, and install grub again (but this time without --removable) to set up the NVRAM entries as they should be.

However, if you actually want to install the BIOS GRUB variant, you still need a special partition because of the BIOS+GPT combination. This time, the "BIOS boot partition" (as the name says, only used in BIOS mode) needs to be ~2 MB, not formatted, and – I think – somewhere within the first 2 TiB of the disk.

Again, more information can be found at:

• https://wiki.archlinux.org/index.php/GRUB#BIOS_systems
• https://www.gnu.org/software/grub/manual/grub/html_node/BIOS-installation.html