Thanks for all the help everyone. Managed to get it to work after re-imaging the USB stick for the umpteenth time with the exact same image. Hope that doesn't mean my (relatively new) Data Traveler stick is dying :(
Typing this from Xubuntu while compiling a computer vision module to make my webcam work for aligning stuff on my laser cutter :C
I would try re-imaging umpteen or so times.
I had no good advice to give around UEFI and Secure Boot.
System Rescue CD does usb and *might* work out of the box. I can boot the newer/est imacs here with it on a usb stick no probs. Dunno about secure boot.