EFIs support programs, including boot loaders, of like bit depth. In other words, an x86-64 (aka AMD64, x64, or EM64T) EFI can launch a 64-bit binary, which normally has a filename ending in
x64.efi; and an x86 (aka IA32, i686 or related) EFI can launch a 32-bit binary, which normally has a filename ending in
ia32.efi. Note that, if you have a 32-bit EFI, the bit depth of the CPU is irrelevant. The result is that your system with a 32-bit EFI and 64-bit CPU is limited to running 32-bit EFI programs.
Normally, the bit depth of the EFI boot loader (which is just a particular type of EFI program) also limits the bit depth of the OS it runs. Thus, it's easiest to install a 32-bit OS on a computer with a 32-bit EFI. There are ways around this limit, though. In particular, both Apple's OS X boot loader and Linux's GRUB support cross-bit-depth kernel booting, so you can launch a 64-bit kernel from a 32-bit boot loader or vice-versa. (Obviously, you need a 64-bit CPU to launch a 64-bit kernel.) Since you say you're using Linux, but don't say what distribution you're using, I can't give very detailed instructions -- and in fact I don't have the details handy. Such cross-bit-depth installations are very much "bleeding edge," and I recommend avoiding them if at all possible.
Sticking with a 32-bit OS is likely to be easier, but many OSes (including most Linux distributions) have neglected 32-bit EFIs, so you may need to add a boot loader yourself. This process is described for Ubuntu here. IIRC, Debian now provides 32-bit EFI support, so you might get it working "out of the box."
Ultimately, to have one disk that's bootable on both 32-bit and 64-bit EFIs, with BIOS/CSM/legacy-mode boot support out of the question, you'll need to install both 32-bit and 64-bit versions of a boot loader, and configure one to boot in a cross-bit-depth manner. It's likely to be better to have two disks, or at least two installations on one disk, one being 32-bit and the other 64-bit. For an external disk, the 32-bit boot loader will be
EFI/BOOT/bootia32.efi and the 64-bit boot loader will be