If you only need shared hosting, Dreamhost is a very decent host. You can have multiple websites in one account, multiple databases, multiple users. Installing Catalyst was kind of a drag since at this point(June 2009) their version of ExtUtils::MakeMaker and Module::Build were too old for local::lib. Use the Dreamhost wiki instructions instead. It feels much more responsive than a previous site that I had at ASmallOrange.
I got local::lib working as of August-09, along with Catalyst from CPAN. An archive (and tarball) is available here. --ew73