If you follow nvidia's instructions for removing packages, you get stuck in a debugging loop where it says "following packages have unmet dependencies".
For some reason nvidia drivers installed through the default Ubuntu installer is always broken, so you'll need to get force purge these dependencies in order to continue.
sudo dpkg --force-all -P <package_name>
Alternatively, apt --fix-broken install
can get you to the point where you can just apt remove
all the packages.