Really? I've always found a liking for the newer UEFI, as windows can't overwrite my bootloader (since it's no longer in the MBR), but I guess it depends on the implementation and how easy it is to choose / add what to boot.
For my machine I can just add an EFI entry if it's not existent pointed on the correct hard disk to EFI\LINUX\grubx64.efi yea windows you won't touch that unless you want to be an ass! lol (hasn't happened yet) I can then re-order them how I like to say boot linux by default :) and it'll even automatically boot a usb with an EFI partition usually or else I use my entry I added for USB UEFI boot. (For the default EFI\BOOT\BOOTX64.efi [and actually I was partly wrong I think this default boot loader does get overwritten when you install a new OS to your EFI, but your bootloaders are still there this is just the main/default one!)
@OP:
Just make sure you're booted via UEFI(so your USB or whatever should have it's own EFI as well and boot from that rather than legacy)
This will check to make sure:
[ -d /sys/firmware/efi ] && echo "EFI boot on HDD" || echo "Legacy boot on HDD"
should return "EFI boot on HDD".
And install grub-efi (instead of the standard grub), and install grub to your efi, you may have to manually mount your EFI partition to /boot/efi first:
root@localhost:/# mkdir /boot/efi
root@localhost:/# mount -o rw /dev/sdX1 /boot/efi
Then do the "grub-install /dev/sdX" as you would, and "grub-update"
obviously replacing the 'X' with your disk that has the OS on it (and if 1 is really your EFI partition which it should be) you can also just use one disk's EFI for booting all your OSs on all your disks, but I'd recommend keeping it straight. That way if you dropped it in another identical or similar box you would have it's necessary bootloader right there and could just boot it! Or swapping disks around you won't be confused on which bootloader is for which OS on which disk :D
Oh and a recent discovery of mine is using efibootmgr to add an EFI boot entry to your nvram, if the uefi bios doesn't make it easy or convenient:
efibootmgr -c -g -d /dev/sdX -p 1 -w -L "My Linux" -l /EFI/LINUX/grubx64.efi
Where /dev/sdX is your disk that contains your OS your installing the efi bootloader for, -p 1 is partition #1 (EFI partition), -L is what you want it to appear as in your EFI boot list, and -l (lowercase L) is where the grub bootloader resides (that you just installed). So 'LINUX' will likely be replaced by your distribution's name, (ex. ubuntu, or arch_grub)
Every disk that you have OS's to boot should (but doesn't have to) have their own EFI partition as the first one and your EFI level bootloaders installed on it in their own directories which keeps your bootloaders neatly in order. (Instead of having to let windows overwrite the MBR bootloader then you have to use a live usb/dvd to fix it back to grub, I always disliked OSs all having to piggyback on the same bootloader starting point (even if you launched another bootloader from the main one for example, they all still like to overwrite the MBR and claim superiority lol)
Also with the GPT/GUUID partitioning everything is a primary partition now, no more messing around with primary+logical, just everything is simpler, everything is a primary partition! :)
Anyway I like to avoid shrinking partitions, I'd say just allocate the space you want for windows and install it to that space, and leave enough room for your linux + swap partition or whatever you need.
I think windows install then linux install is still the desired order of operations even with UEFI, but with UEFI I'm confident that even if windows overwrote my default efi bootloader, that I could manually force it to boot my linux install without having to rewrite the bootloader, because my bootloader is still there and hasn't been overwritten! So that's the main difference I like about uefi compared to legacy.
There that should cover the basics of UEFI, and I'd recommend you install it using UEFI rather than legacy. Legacy might seem to make things simpler right now, but you have a uefi machine so you might as well get comfortable with it!