I'd avoid VPS providers in general, but AWS is on a whole different level than linode. They actually understand what they're doing well enough to do live xen patching etc.

But yeah, people get hacked through their hosts all the time. Best approach is colo with minimum access for the dc staff.

That's been my recommend for a long time. Plus, I liked obfuscating with unusual CPU choices and network guards (esp for protocol layers). Worked wonders with about no effort outside setting up guards. Opponents throw so much x86 shellcode at your Alpha, etc boxes while never quite getting stuff to run.