Ok, yeah, Cloudflare would work very well because, I think, the issue is with the PHP parsing which would be on the server. Not much Cloudflare can do there. That why you need a caching plugin like W3TC.
Rackspace … is that their CloudSite service you’re using? I used them briefly for this site (I moved to a managed VPS) because I thought I could scale as needed. I found that it to be much slower than when it was hosted on Bluehost at their Business Pro service level (which actually worked pretty darned wull in hindsight). The speed was actually even worse when I used W3TC on CloudSites. WP Super Cache seems to work much, much better … at the very least I suggest try switching to it.
You may find this artical enlightening:
Looks like Site Ground Go Geek Plan would be quite nice… as well is InMotion Business Hosting Pro for shared hosting.