Sarà estremamente difficile: il fornitore avrà accesso fisico alla macchina e non lo farai. Peggio ancora, il tuo sistema verrà virtualizzato da qualcuno diverso da te, il che significa che se sei paranoico, non puoi nemmeno fidarti del tuo sistema operativo.
Anche con la crittografia completa del disco, avrai difficoltà a impedire a qualcuno dello staff di accedere ai tuoi dati (a meno che non lo decifri mai, il che significherebbe annullare il punto).
Quindi in sostanza, se non ti fidi dello staff della società di hosting, non preoccuparti di cercare di bloccarli. Non lo farai. Scegli invece una compagnia diversa. E se non ti fidi di nessuno con i tuoi dati, controlla l'hosting in-house.
A parte questo, i server VPS non sono così diversi dai server dedicati, dal punto di vista della sicurezza. Assicurati solo di rimuovere le possibili chiavi SSH autorizzate preconfigurate che alcune società di hosting aggiungono ai loro modelli di macchine virtuali per scopi di manutenzione, e blocca la scatola come faresti per bloccare qualsiasi macchina Linux sensibile.
I tutorial di Linode sono un buon punto di partenza se non sei sicuro di cosa fare.