> sudo apt-get install --fix-broken --fix-missing
apt-get: relocation error: /usr/lib/x86_64-linux-gnu/libapt-pkg.so.5.0: symbol _ZNKSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEE7compareERKS4_, version GLIBCXX_3.4.21 not defined in file libstdc++.so.6 with link time reference

# Download the deb files in the right versions for 16.04:
> wget mirrors.kernel.org/ubuntu/pool/main/a/apt/apt_1.2.10ubuntu1_amd64.deb
> wget security.ubuntu.com/ubuntu/pool/main/g/gcc-5/libstdc++6_5.4.0-6ubuntu1~16.04.2_amd64.deb

# Removing this specific version, which blocked installing the correct libstdc++6:
> sudo dpkg --force-depends -r libstdc++6:i386

# Then install the "good" version from the file:
> sudo dpkg --force-depends -i libstdc++6_5.4.0-6ubuntu1~16.04.2_amd64.deb

# Now, just install apt from file:
> sudo dpkg -i apt_1.2.10ubuntu1_amd64.deb

# And finally, fix the mess I left while updating and trying things out:
> sudo apt-get install -f --fix-missing
> sudo apt-get autoremove