Juanito's excellent instructions (first post of this thread) are the best I could find anywhere on the internet detailing how to set up a usb stick that can boot in both BIOS and UEFI machines. Thank you, Juanito!
I just did two things differently.
1. I used gdisk instead of fdisk
UEFI requires a GPT partition table. fdisk does support GPT, so I don't think it matters much whether you use gdisk or fdisk. With gdisk, I discovered that I didn't have to specifically request a GPT partition table--it automatically uses GPT when creating partitions. Note that if you use gdisk to add partitions to a disk that already has an existing MBR table, the MBR table gets converted to a GPT table (gdisk warns you about this). Fortunately, in my experience using gdisk on multiple disks, this happens without any loss of partitions or data. (You should backup your data before doing this, of course, just to be safe.)
2. I put a BIOS boot partition on the disk:
$ sudo gdisk /dev/sdc
...
Number Start (sector) End (sector) Size Code Name
1 2048 52430847 25.0 GiB 8300 Linux filesystem
2 52430848 52432895 1024.0 KiB EF02 BIOS boot partition
3 52432896 53481471 512.0 MiB EF00 EFI system partition
The BIOS boot partition only needs to be 1MiB in size and you do not need to format it or put anything in it. It just needs to be present, otherwise this step from Juanito's instructions results in an error (something about grub-install having no reliable way to install the target):
$ sudo grub-install --target=i386-pc --boot-directory=/mnt/sdc3/EFI/BOOT /dev/sdc
So in this partitioning scheme:
* TCL directories (/boot and /tce) go in /dev/sdc1 (same place as in Juanito's instructions)
* You don't have to do anything with /dev/sdc2 other than create it--grub-install takes care of the rest
* The only file you need to manually create in /dev/sdc3 is /dev/sdc3/EFI/BOOT/grub/grub.cfg