We have added full page caching to Magento (126.96.36.199). The pages, once cached, open immediately. However, when a page is being viewed for the first time, it still takes ages to load. What is the best way of speeding up the first view of a page?
What you are basically asking here is how to improve the performance of your store - it's not anything to do with the full page cache you are using as the first view of each page is the uncached performance of your store.
I don't know what exactly you mean by pages 'still taking ages' to load, but if you are finding the performance unacceptably slow then you need look at your server hardware. FPC is not a magic bullet so if you have implemented it to fix poor performance or your store uncached, you've done it for the wrong reasons. FPC should be implemented on stores with already acceptable uncached performance to further improve performance and reduce required resources by the server.
Remember that certain areas of the store will always be uncached like the cart/checkout and customer account pages, so you must ensure you store performs acceptably before you even look at FPC. If you found a store that performed pretty well when selecting products, but then ground to a halt when you tried to checkout, would you stick it out or just go to another store? I know what most people would do. Basically slow checkout = lost sales.
I wrote a blog post a while back on the three main areas you need to look at when improving the performance of your Magento store, but to summarise the first area you need to look at is getting the right hosting. The hardware your store runs on is the foundation for everything you do and if this doesn't have the raw power to run the store well you are never going to get the kind of performance you need.
The second area you need to look at is the time it takes for the first request to complete. When this request returns content the page starts to render in the browser, and until that happens the user will see nothing at all. This is key in giving the perception of good performance even if the rest of the page takes a little while to render fully as assets are collected and onload JS events fire and so on. This time is what FPC (Varnish included) improves, but you should aim for say 1-2 seconds here without caching, that way you can be sure the checkout will still be acceptable fast.
The third area you need to look at is the number of assets on the page, so images, CSS and JS. Reducing JS/CSS is pretty straight forward - just turn on merging in admin, but images is a lot more difficult as if you have a lot, it will likely require design decisions to be made to reduce the number of images you use. 60 assets or less is decent, but if you can cut this down to 30 or less, or use sufficient CDN's to spread the requests you will see much faster times for the page to finish loading entirely.
You may be interested in trying out our performance profiler which will give you information specific to your store on the above.
Without code this is pretty complex to solve. Try using http://gtmetrix.com/ and https://developers.google.com/speed/pagespeed/insights/ to identify where does the slowiness comes from.