Ciao!
Per un buon provider devi vedere quanti altri siti schiaffa su quel server e con quell'IP... un buon toollino e' questo:
http://whois.domaintools.com/

che ti dice quanti altri siti sono col sito ricercato. Questo perchè lo spider fatica di più in una macchina dove dentro c'e' un buglione di file.

Ergo, il server dedicato e' ottimo, ma l'IP dedicato va proprio bene e poi puoi chiedere al provider quanti siti ci mettono di solito per server fisico, te lo dovrebbero dire.

Per altro, bhe certo i downtime, ma se ce ne ha così tanti da essere un problema prima o poi gli utenti se ne vanno e la baracca chiude, quindi magari uno che e' li da tempo...

Ah si, un'altra cosa è la locazione dei server. Se i tuoi utenti sono negli stati uniti compralo li per tempi di accesso più corti, sennò ovunque tu abbia lo zoccolo di utenti

Poi ci sarebbe la scelta del database, il tipo di sistema operativo del server, i servizi che ti danno e via e via, ma per l'indicizzazione e ottimizzazione direi che così può bastare.