Dipende molto dalle tue esigenze e quanto vuoi spendere, ma di provider "low-cost" con servizio quasi impeccabile che ho personalmente usato, ci sono: Hetzner, Netcup (guarda i rootserver), php-friends
Ovviamente considera che io le uso a livello praticamente amatoriale/hobbistico, a livello business i requisiti possono anche essere molto diversi dai miei
E mi sa che devi assumere qualcuno esperto che se ne occupi, con la roba unmanged non si scherza (disaster recovery, sicurezza, aggiornamenti, ddos ecc..)