You should run static page caching. WP Super Cache, W3 Total Cache etc. are a pain sometimes, but if you switch to Varnish or a simpler caching plugin (like Batcache) then you will find things run a lot smoother. Of course, you can't run the more advanced caching plugins without upgrading to a better host first, since most of them don't support such features :/

The performance advantages to running static caching a quite enormous. If you do load testing on your site (Apache Bench is useful for this), then you can see exactly how much of a difference that extra caching layer can provide. Even adding a simple object caching layer can cause massive improvements to page load times and total load capacity.