I've found the hardest thing about multi-hosted services (many host accounts on one machine) is that even if you have them install your Perl module, your site may be migrated to another machine at any time. The most important thing about such hosting services is if you have shell based access on your hosting server. Not root, necessarily, but just a plain old shell account in which you can manage your site.

All other things being equal (CGI w/ Perl, reasonable disk space), having that shell account gives you the ability to install your modules in personal space. Obviously, some of the "horse pill/kitchen sink" modules are probably not suited for this type of installation, but if you are careful you can get what you need without asking for help.

For example, I work on a site for a neighborhood association. I like Template::Toolkit, but because of the redeployment of assets, I had it then lost it as a system module. However, I have installed it in the site's tree, and just make sure my @INC knows where to look, and I'm good as gold where-ever they move the site next.