TL;DR Don’t be hasty when mucking around with graphics drivers
What caused problems
After updating to Ubuntu 16.04, steam was no longer starting. Some forum posts were suggesting that certain dependencies weren’t being linked correctly and suggested manually moving things around. That didn’t seem to do anything, so I tried updating the graphics driver. I was a little hasty, and being unsure of which driver was in use, I decided to apt-get remove a bunch of other drivers, including the nouveau one. This caused everything to break and lightdm wouldn’t start properly, which means I couldn’t log in anymore.
First order of business was to get a terminal, since lightdm hanging meant I couldn’t log in normally. Recovery mode was too locked down for me to get anything real done, and it would freeze when I tried things. I ended up editing the boot option and removing every additional argument past “ro” and replacing it with “text”. This allows you to boot into terminal mode.
Next, was connecting to wifi. Now, I think my system was automatically connecting anyway, but I figured it out at any rate. nmcli dev wifi list shows what are available. nmcli dev wifi connect “SSID” password “PASSWORD”
I ended up doing sudo apt-get purge xorg lightdm and reinstalling with sudo apt-get install xorg lightdm, which took FOREVER, but it did get me back to a graphical boot after restarting. I now think this was probably unnecessary. It ended up defaulting me to an older proprietary NVIDIA driver that steam was still interacting poorly with, but at least I could use the computer now!
Finally, I discovered through this post that I could run ubuntu-drivers devices which displays a list of available drivers, and sudo apt-get install whichever driver I wanted. Picking the latest proprietary NVIDIA driver finally let me run steam without issue.