After a ton of searching, I a) found what the hardware problem was, and b) realized that I can use the install media as the installation source - that might sound obvious, but the keyword there is "can", not "should be able to". It's badly documented and very not-obvious.
Anyway, here's the source for using the install media. Part of the install process is choosing which sets of packages you want to include - things like OpenSSH Server stuff or Mail Server stuff. There's also one called Manual Package Selection. It didn't seem to do anything during the install (though I did walk away, and it might have timed out), but you can reenter the tool after the installation is finished and you've rebooted into the new OS.
After rebooting, log in and plug the ubuntu server install media into the computer. Run:
sudo tasksel install manualThis command will find the install media, and 'install' the manual package selection 'package'. In other cases, it would actually install stuff - in this case, it just gives you a shell prompt. At this prompt, you somehow have full internet access - I don't know how it happened. It was automagical. In my case, the next step was editing the sources list to enable the universe repository (already seemed enabled - automagic of the tasksel command?). Source on the actual internet driver fix.
sudo nano /etc/apt/sources.listAnd a line that looks like this
deb http://us.archive.ubuntu.com/ubuntu/ xenial main restricted
Should be changed to look like this:
deb http://us.archive.ubuntu.com/ubuntu/ xenial main restricted universe
[ctrl]-x to leave. Then, run
sudo apt-get install r8168-dkms
And the driver is installed. Reboot and the internet should work.