En general, salvo algunas excepciones (límite de memoria a 256/512MB), casi cualquier proveedor podría cumplir con los
requerimientos que pide Magento a nivel técnico.
Pero más allá de lo técnico, también intenta hostearte en una empresa con trayectoria confiable y un tiempo en el mercado, y que no sólo te brinde buenos precios y toneladas de prestaciones, sino también un buen soporte técnico y medios confiables (no sólo electrónicos) para contactarte con ellos en caso de necesitar asistencia.
Saludos,