I should point out that Internet Recovery is not always available. You may find no problems using Internet Recovery at some later time.
I would image that far more users create Linux installers from Windows, than from macOS. For example, the Ubuntu instructions for Windows users requires you to use Rufus to create the USB Ubuntu installer flash drive. Rufus runs on 32/64 bit Windows 7 or newer. Any Linux installer (including Ubuntu) will allow you to erase the installation drive and install a clean version of Linux. This usually is the easiest of the installation options.
Note: You can also use etcher. When testing, I found etcher created an installer which boots to the Grub menu. This can be useful, if you have problems booting Ubuntu live from the installer.
You may choose to keep Windows and replace macOS with Linux. Or, keep Windows until you are sure you want whichever version of Linux you choose. In this case, the procedure to install Linux can be more complicated, if your current Windows BIOS boots. BIOS booting Windows and macOS dual boots require the installation drive to be hybrid partitioned. The Linux installer may not work properly with hybrid partitioning in place. You may need to first boot to a live version of Linux (such as Ubuntu) and run a partition tool (such as gdisk which is include with Ubuntu) to document and remove the hybrid partitioning. Once Linux is installed, you usually can reinstate a different hybrid partitioning for a Linux and Windows dual boot.
I suppose there a versions of Linux which are installed so as not to appear in the Mac Startup Manager. This is where the option key is held down during startup. (Ubuntu does appear in the Mac Startup Manager.) Also, many versions of Linux have an option to be installed with Grub. In these cases, you may also what to install the rEFInd Boot Manager.