bien, en lo que respecta a proveedores españoles no hay mucho para escojer, quizas en hostigal encuentres, pero es algo que saldrá muy caro en comparacion a las empresas con servidores en USA.
Sobre tu necesidad de que estén en españa físicamente, no le veo mucha diferencia, pues por ejemplo, este foro se aloja en USA y desde españa y todo el mundo se lo puede visitar sin problemas, por lo que es algo trivial.
¿El SEO? al ser dominios .es google automaticamente los geolocalizará con España, por lo que esa parte también es trivial.
Y lo del vps, claro... tráfico = consumo de ram y cpu, lo que en un shared es algo muy valioso y cuidado por el sysadmin. Si tus sitios consumen mucho no te quedará más remedio que el VPS.