Why can't (and how can) I install both grub-pc and grub-efi packages?

Drop down a level in the packaging, and install grub-pc-bin and grub-efi-amd-bin. Those packages wont conflict, but neither will they install grub as an active bootloader nor update grub.cfg on upgrades. Install the top level package of your choice for the update functions: grub-pc or grub-efi-amd.

There is only one /boot/grub/grub.cfg file, so you have to choose which format to use for it (legacy or UEFI) (they're not much different, but some things like the chainloader command are quite different).

Updated answer on Sep 27, 2020:

Based on additional experience, I can now update my answer.

Presumably your goal (beyond merely installing packages) is to actually make a disk that can boot on both BIOS and EFI systems.

If you have a disk that can already boot on BIOS systems, you may be able to add EFI boot capability by running the below commands. Please note that (1) the disk will need to have a valid, properly formatted ESP (EFI System Partition), (2) the ESP will need to be mounted at /boot/efi and (3) the disk may need to have a GPT (GUID Partition Table) rather than MBR (Master Boot Record). Assuming all that, the following commands worked for me:

$  sudo  apt-get  install  grub-efi-amd64-bin
$  sudo  grub-install  --force  --removable  --target=x86_64-efi  \
     --efi-directory=/boot/efi  --bootloader-id=Ubuntu

If you have a disk that can already boot on an EFI system, you may be able to add BIOS boot capability by running the below commands. Please note that (1) your disk may need to have a GPT (which it probably does) and (2) if your disk has a GPT, the GPT will need to specify a "Legacy BIOS boot" partition. Assuming you meet these preconditions, the following commands may work for you. (I have not tested these commands, but I suspect they might work.) Replace /dev/sdX with the appropriate device (often /dev/sda).

$  sudo  apt-get  install  grub-pc-bin
$  sudo  grub-install /dev/sdX

In either case, it probably does not hurt to rerun update-grub after making the above changes.

$  sudo  update-grub

For your reference, here is the Grub documentation.

Aside: I can view my GPT partition table by running sudo gdisk -l /dev/sdX. For example, my Legacy BIOS boot partition looks like this:

Number  Start (sector)    End (sector)  Size       Code  Name
   1              34            2047   1007.0 KiB  EF02  2004_bios_boot

Note that ubfan1's answer said that difference between the configuration files for the "legacy" and "UEFI" versions of Grub may cause problems. While such differences exist, I think they may not be relevant (or may only be minimally relevant) to this situation. "Legacy Grub" is version 1 of Grub. Whereas "Legacy boot" is booting via BIOS. Grub version 2 (commonly called "Grub") does support both BIOS and EFI booting. So don't confuse "legacy Grub" with "legacy booting".

Original answer on Sep 18, 2020:

As described in ubfan1's answer, you can install both grub-pc-bin and grub-efi-amd64-bin.

But note that there are some files in the grub-pc and grub-efi packages themselves. It appears that the files themselves all have distinct paths. So the files themselves do not conflict.

https://packages.ubuntu.com/focal/amd64/grub-pc/filelist
https://packages.ubuntu.com/focal/amd64/grub-efi/filelist
https://packages.ubuntu.com/focal/amd64/grub-efi-amd64/filelist

As for why the restriction is imposed, I can only speculate. Some possible reasons:

1. If you look at this answer, it appears to be recommended to install the EFI version of Grub from inside a system that booted in EFI mode. So it is possible that EFI Grub is installed in a system specific manner.

2. It is possible that the Ubuntu developers do not want to support multiple bootloaders on the same system. It is probably difficult to test and provide QA for such a setup.

3. It is possible that both EFI and BIOS Grub are configured to use the same configuration file (probably /boot/grub/grub.conf). (And, as ubfan1 mentioned, the EFI vs BIOS versions of Grub may have different capabilities.) I believe this is an arbitrary limitation, that is, different installations of Grub could be configured to use different configuration files.

As an aside: I recently converted my BIOS system to EFI. It seems that the disk can (at least at present) successfully boot in either mode.

If you want to create a disk that boots in both modes, I would recommend installing the whole OS in EFI mode, and then manually trying to add a BIOS version of GRUB (or using Syslinux). I say this because I have much more experience installing and troubleshooting BIOS bootloaders. An EFI expert might recommend the reverse.

Why can't (and how can) I install both grub-pc and grub-efi packages?

Live Ubuntu systems

Both packages can be installed (and are installed) in live Ubuntu systems. You have a live system in a USB drive that is cloned from an Ubuntu iso file.

Installed Ubuntu systems

In the current versions of installed systems you must remove the installed program package in order to use the other one.

We can only guess why this is so.

Switching between the two grub packages makes it possible to create installed systems that can boot both in UEFI mode and BIOS mode (alias CSM alias legacy mode). See this link.