You have to chose to trust
something. If you keep falling in this rabbit hole of not wanting to trust anything, your only option will be to stay on an airgapped computer, or even ditching that for a paper notebook in case the hardware manufacturers did something. That's unless, of course, you have the time and resources to manufacture your own computer down to implementing every piece of circuitry in each microprocessor.
I think chances are pretty slim that a VPS company's vps isolation is so crappy that you have the chances of getting your vps hardware shared with someone that knows of such a gapping security hole that could be such a huge liability to the VPS company.
EDIT: Also, why would someone go out of their way to compromise a neighboring VPS, check if they, by chance, have a package repository, and insert malware in that? Who are you, that someone would think that's a good use of their time?
You know, society can't function without trust. Every person that's close to you could suddenly turn around and try to kill you, but you have to trust that they function by reason, and know that they have no reason for doing so. Locks around the world are pretty useless to keep strangers from lock-picking them and very many of them are keyed-alike. Their real reason is to simply make it a greater hassle to get to whatever they're protecting and therefore make it a less appealing target. Like so and with other methods, people implement their security by making themselves a less appealing target. Some people setup the outside of their home as a dump while building a mansion inside. These people trust robbers to act on reason.
No one has perfect security. Security is a matter of choosing what to defend against (your threat model), choosing what you can trust, and anchoring your defenses on the things you trust.
EDIT 2: I removed the paragraph on VPSes being virtual in name only. Linode apparently uses KVM.