Before you ask: "Did you try to optimize WP to run faster first?"

YES! For months I've been trying CDNs, caching plugins, reducing the number of plugins, minifying scripts, optimizing images...

The whole architecture of WP and our theme just has too much cruft.