1.
Ich habe keine Empfehlung zu Shared-Hostern.

2.
Ich kenne Deinen Hoster (vermutlich) nicht und weiß daher auch nicht, welche Hosting-Pakete er anbietet.
Ich habe auch keine aktuellen Vergleiche zu Shared-Hostern.

Als ich mich mal vor Urzeiten umgesehen hatte, gab es Pakete wie Basis, Medium, Premium mit verschiedenen Umfängen, was damit möglich wäre; Z.B. "gar kein Perl", "vordefinierte Perl-Skripte (Gästebuch, Form-Mailer, ...)", "eigene Perl-Skripte".

Daneben wäre jeweils das "Kleingedruckte" zu beachten, zu was sich der Hoster jeweils bereiterklärt.
Z.B. ob er einen Hinweis gibt, dass Perl-Module bei Bedarf durch den Hoster nachinstalliert werden können.
Wenn er das ausschließt (entweder direkt im Kleingedruckten oder auf Nachfrage), würde ich die Finger davon lassen und beim nächsten Hoster schauen.

Abschließend: Würde ich nochmal einen Webservice in irgendeiner Art brauchen, würde ich es mittlerweile eher als (v)Root-Server aufziehen.
Auch wenn das potentiell heißt, dass ich mich selber ganz um das System kümmern muss (Updates, Zugang absichern, Backup, ...). Aber dafür kann ich mir dann alles so einrichten, wie ich es haben will.