Find a better host is the short answer, specially if they have absurd caps
on CPU seconds you can use, amount of memory per process or
number of database queres.
The long answer is to try to find what real bottlenecks your particular host
has. Are they CPU starved? Are they database bound?
Install the devel module to see how many queries you have per page. Try
to cut down the number of modules you use.
Read a bit on the tools and resources here
http://2bits.com/articles/drupal-performance-tuning-and-optimization-for-large-web-sites.html