The best way to optimize Magento's performance is to use its Compilation function. It has proven to be stable and reliable even though it is still in development. The performance increase is between 25%-50% on page loads.
You can enable it from your Magento admin panel. There from the top menu choose System > Tools > Compilation.
If the above performance improvement is not enough try to find a Magento optimized web hosting.