T2 Mac with empty internal storage won't boot from install USB

Ahhh… Catch 22 mistake, I'm afraid.

You can't boot to USB with Secure Boot on & you can't toggle Secure Boot settings without an admin account, which was of course erased when you formatted.
You will need to use Internet Recovery to get back to a state you have an admin account, or take a trip to an Apple Store, with proof of purchase.

See Apple KB - About Startup Security Utility

I did eventually get Internet Recovery working. I was getting various errors (-1008F, -2106F and perhaps others) after long periods of time spent waiting for the boot to complete. While some of these may have been down to a shoddy internet connection, it seemed as if it would just error immediately after the bar had reached 100%.

After doing a bit of digging I removed the Mac from my iCloud account via appleid.apple.com as well as perform all steps on this guide to restore a Mac with Apple Configurator 2 (I found about that on this thread). You will need an additional Mac on hand to do the latter.

After doing that, then booting with Internet Recovery and then reinstalling from the recovery menu I still needed to log in using my iCloud credentials as well as my old local account. Fortunately for me that wasn't a problem at all, but bare that in mind if anyone reading is in a similar situation!