How to improve unexpectedly poor Craft performance?
This is a great resource on improving performance as it's a multi-pronged attack:


Native craft caching {% cache %} which you mentioned you have done
CDN and Browser caching
Varnish and other tools, including plugins like Cache Warmer


I concentrated on cache as this is usually where the bottleneck seems to happen in Craft. Apologies if you've addressed all these already!