I tried disabling fast boot (both Windows and UEFI), checking the cables, manually setting the stuff DHCP would've set up, and disabling power efficient Ethernet in Windows, but none of that helped Also I'm having no issues on Windows
Solution
Found a bandaid fix: I have to completely power off the PC (as in turning off the PSU) and then it works