FastCGI, period. Either use mod_perl or FastCGI but not CGI (plain evil memory eating stuff).
Generally, FastCGI is used with Lighttpd or other web server in front of Apache (proxy stuff). You also need to consider memory footprint. Check out following docs:
Six Apart Developer Documentation - FastCGI Benchmarks for Movable Type