I think this is a side effect of the many package managers out there, and unfortunately, is the nature of the beast. Your VPS has chosen to image a version of Ubuntu that has fewer packages installed than your Vagrant VM.
That's pretty weird that you're seeing some rbenv errors -- I'm not sure how they're related to python-apt. I'm a bit out of my league here (since these are both parts of the Ruby toolchain), but I think you'd benefit from reinstalling the latest version of rbenv and ruby-build via apt.