While I certainly don’t want to start a game of pingball with your web host, unless you have a dedicated server and your site is the only one on it then that doesn’t necessarily provide as with a lot to go on, since – assuming for the moment this is actually a regular shared hosting plan – those formidable resources will be split across all the different sites/accounts that share that particular server.
Beyond what Chris has suggested, then, I’d recommend setting up an appropriate level of caching and possibly also jumping to a hosting plan that can better accommodate this situation – right now I’m afraid there is little else for us to do or suggest (and keeping in mind that, as above, we are continually working to improve performance across the board).