We have just deployed our first Magento store and I too was looking to optimize the store to get faster response times and we concluded that for small stores it boiled down to processor speed on your server.
We have been running our client sites in a three tiered VPS set up that includes a dev, staging, and production server. The production server is set up as follows:
CentOS 5.2 (64 bit)
1/2 CPU allocation (this appears to be the most critical and as store traffic increases you simply up your CPU allocation)
Our web host is http://www.hostcube.com and they can configure whatever you need.