CGI thats used heavily is going to be rough on most servers. Try to look at alternatives like mod_perl. If a script is written well, it can be run through Apache::Registry with little effort. This will take a lot of the load off but most hosts do not offer it.
Heres a guide to porting your apps. http://perl.apache.org/docs/1.0/guide/porting.html
Feel free to pm me if you need help with the perl.
That said getting larger plans from a host can get you on a lower contention server. Your requirements are pretty low besides processor, so a VDS might work well too.