Hola, en mi opinion no deberías contratar una empresa ( te prometen mucho y al final solo te sacan el dinero ), sino mas bien a un seo que te ayude.
Te podría decir un montón de ellos muy buenos ( Errioxa -
http://www.mecagoenlos.com, adseok -
http://www.adseok.com, Duque -
http://www.seoprofesional.com... ) intenta optimizar tu mismo la web buceando por los blogs y si no das, pues intenta llegar a un acuerdo con alguno, pero siempre a nivel particular.
Fijate en un detalle, si la empresa que te recomiendan tiene publicidad en adwords, no la
contratates, si no es capaz de posicionar su propia página como te posicionará la tuia.
Un saludo.