Apparently macOS Internet recovery is fucked in Australia. Holding Cmd+R while booting takes you into internet recovery. Log into a Wi-Fi network, and then a spinning globe will appear. Wait a while, around 20 min and it should show a loading bar and say that its "Starting Internet Recovery". If this fails with error 2002F and you are in Australia, try switching your DNS to Google DNS, and then restart and try again.
Found this solution in this thread.