If you can at all manage it, don't run as a CGI. Use FastCGI or mod_perl. That'll immediately cut the overhead of each request by a large amount. And see the excelent mod_perl guide for mod_perl specific tips.

If you must have real CGIs, fork off a child (or pass off the work to another persistent process) to finish any long running tasks after you've interacted with the browser. That'll let the httpd you're interacting with go on and service another request.