There are only 3 areas you need to look at when optimising the performance of your store - hosting, time for the first request to complete, and the number of requests per page. You may be interested to read our blog post, and also use our performance profiler, but to summarise:
Hosting - this is of course the foundation of your entire site and performance can only be as good as the hardware your site is running on allows. You do need to have acceptable page load times on uncached pages, and this is purely so that you maintain performance on pages which should not be cached such as the cart and checkout.
If the site suddenly becomes very slow when you go to checkout, you are likely to lose customers, so the right hosting properly configured is a must as a starting point (who you host with doesn't matter). Important rules though - always steer clear of shared hosting when it comes to Magento, and host on a server geographically close to you and your main target audience.
Time for first request to complete - by this I mean the time it takes for the server to generate the HTML in response to each request, excluding the time it takes for your request to reach the server, or the response to reach the browser after being sent by the server as these are connection dependant. This request is extremely important as only when this has completed will the user start to see anything render in their browser at all. It's this time which all FPC solutions (Varnish included) improve on so the user will see content start to render in their browser more quickly.
Number of request per page - while the above affects when the page will begin to render, the number of requests on the page affects how long it is before the page has loaded entirely with all assets - so images, JS and CSS. FPC will have no affect at all on this.
Every image, JS and CSS file which loads on your page is gathered via it's own request to the server. Every request takes a finite time to complete so you can therefore logically see that the more assets you use, the longer it takes for the page finish loading. Additionally the more requests you have the more requests queue and are idle as only a few requests can be sent at any one time - the makes page load times even longer.
Reducing the number of JS and CSS assets is straightforward - just turn on merging, but reducing the number of image assets is harder and requires you to review your page design and basically determine where images can be removed. You can also often reduce the number of images by combining smaller images into a very few single image 'sprites' or by leveraging more capable CSS3 styles to achieve things like rounded edges and button graphics which would historically have been done using images.
Around 60 requests per page will give decent performance, but 30 is a good target to aim for.
In your specific case...
Your hosting looks fine - I am seeing max HTML generation times of around 1.3 seconds for non cached pages, most of time around the 400-500ms mark. So on the first 2 points above you are looking ok.
The number of requests per page - this is where your main issue lies. I am seeing around 120 to 150 requests per page and this is very high. The first thing you should do is turn on JS merging which will reduce the number of request by around 50-70 (depending on the page).
You also however have good scope for creating sprites to reduce the number of image assets. There are around 75 images loading on the homepage alone, but many of them are small icons and buttons which can be combined into one (or very few) sprites. You have the potential to reduce the number of requests per page by an additional 40-60 here.
By enabling JS merging and creating sprites there is a very realistic chance of coming pretty close to the 30 request target for many pages, you will see a very marked improvement in complete page load times by doing this.
A word on FPC. It's not that it sweeps the problem under the rug, it's just thats it's clearly not sensible to have good performance on cached pages and poor performance during checkout. If however you do have acceptable uncached page performance then a FPC cache solution is a good choice to further boost the performance of your store. It is however important to test any FPC solution you implement to ensure the cache is being properly updated when it needs to be, for instance when a product goes out of stock. Many solutions are incomplete when it comes to regenerating cache content when needed. Also Lesti_Fpc is a popular free choice and performs reasonably well, but you will see better performance with some (but not all) of the paid solutions that are available (significantly better with ours).