I recommend Pair Networks - click the add banner at the top of this page.

I've used them for several years (the $29.95/month "Web Master" plan) to host an ecommerce site, and have never had any problems.

I use cpan to install modules to a local ~/libs directory, and all my cgi scripts point to that with the "use lib" statement.