You know you might want to look at loading modules remotely using SOAP or adding code refs to @INC. Then you won't need them on the machine at all. You might have performance issues but you could maybe load them all into RAM with mod_perl.

Anyways most often for general CGI work I find myself using the following

Email::Valid
Tie::IxHash
Date::Calc
Html::Template
File::Find
CGI::Application
Class::DBI