Boot in UEFI mode

You’re on the right track. Shrink the existing partition by a little bit, create a new EFI System Partition (ESP) in the space, and install a Linux boot loader on it. A few caveats:

• I do not recommend using GRUB for this task. You may need to hand-craft your configuration file, and with GRUB this is far too difficult to do. Instead, select almost any other EFI boot loader for Linux that you like. My own rEFInd is likely to be easy to set up, and will enable users to boot other installed OSes, too. (OTOH, you might not want that last feature.) ELILO and SYSLINUX are also likely to be relatively easy to configure. If you expect to update your kernels on the drive, be aware that most boot loaders will require updates to their configuration files to match. (rEFInd is an exception to this rule; it auto-detects kernels on each boot.)
• You must install your EFI boot loader as EFI/BOOT/bootx64.efi on the ESP. (Assuming you’re targeting 64-bit systems.) Normally, EFI boot loaders go to other names and register themselves with the computer’s NVRAM; but to boot on multiple computers, you must use the fallback filename of EFI/BOOT/bootx64.efi. My EFI boot loader installation page covers this topic in more detail.
• EFI systems normally boot from GUID Partition Table (GPT) disks. Your USB drive probably uses the older Master Boot Record (MBR) partitioning scheme instead. In theory, MBR should be OK, but you should be aware that an MBR ESP has a type code of 0xEF. Also, it’s entirely possible that some computers will refuse to boot from an MBR flash drive. If you run into this problem, you may need to convert from MBR to GPT. You can do this with gdisk, but then you’ll need to re-install a BIOS-mode boot loader.