Yo te propongo que mires la primera pregunta de otra manera:
Tienes conocimientos como system admin? Eres capaz de montarte tu propio LAMP y debuguear posibles errores? Necesitas mas control sobre todo el servidor en si mismo: instalar servicios adicionales (mail, dns ?), configurar los servicios instalados para adaptarlos segun las necesidades (en mi caso, tuve una vez que darle mas preferencia al apache que a mysql y por lo tanto me toco retocar las configuraciones), tener acceso a todos los logs?
Si es que si, pues pillate un vps.
Respeto a la pregunta numero 2, yo recomiendo
Mediatemple.net. Yo llevo casi 2 años ya con ellos (con el (ve) Server de 512MB) y estoy muy muy contento. Son un poquito mas carros, pero son muy profesionales y dan muy buen servicio y atención al cliente.
Tienes a elegir en mediatemple, si bien quieres el (gs) de alojamiento compartido o el (dv) para seguir teniendo un dedicado pero con un panel de control ya instalado, para no liarte en instalar LAMP u otras cosas en el (ve).
Mi configuración en el (ve) de 512MB Ram: LAMP + Mail (con antispam) server + ISPConfig como panel de control