I found WP Tuner to be very helpful in understanding what was hurting responsiveness of my blog. Once you install and activate it, it hooks the hookable operations in wordpress and tracks execution time, query count, query time and memory usage at each step.
One thing that is immediately obvious is that startup is an expensive process. It happens on every page load, and accounted for 30-50% of the execution time in most cases. If you need finer-grained profiling than WP Tuner can achieve via the available hooks, you can go in and add one-line timing statements wherever you want. Doing so showed me that plugin loading was the most costly part of the startup process. Some plugins were worse than others, but even the quickest loading plugins still added up.
The only way I found to really improve startup times was to set up a test machine and install APC which caches already parsed PHP code to speed up execution. Unfortunately, I couldn't take advantage of this on my shared hosting. I expect the same is true with most other shared hosts, because I think it increases baseline memory requirements, and may create security issues. There are some shared hosts, like Webfaction, that give you your own Apache instance and let you do pretty much whatever you want with it. APC should be an option for any dedicated host or VPS.
The next thing you can do is optimize database use. The quickest path is to use something like WP-super-cache that can cache the HTML from generated pages, but you've already found the disadvantage of this approach, dynamic elements of the site get frozen until the cached copy is expired.
Fortunately WordPress has an object caching framework that can cache at a finer level, so you can still take advantage of dynamic page generation, while caching the results of database queries and the like. One option is to use a simple file based caching backend. I've been using this, which seems to help. It looks like this does something similar. Some people have reported that their shared hosts have complained about the disk IO this approach causes, but I've had no trouble.
There are other back-ends as well. One for APC, another for MemcacheD, and perhaps others. As with APC itself, these probably aren't an option on most shared hosts.
These things should help with responsiveness when your traffic is low as well as high, and they should help your ability to ride out traffic surges.
There is a lot more in the WordPress documentation, but I'd suggest starting out with WP tuner so you can get a handle on where time is being spent on the server-side.