For example, petsmartfeedback.com is ranked around 10,000 in Quantcast and they have only about 200,000 visits/month. Are you in the top 10k?
If that petsmartfeedback site ran WordPress with a few plugins, Linode plus NginX, I bet the CPU would be easily under 50% all day long with no cache plugin. I think you will run out of bandwidth before you run out of Linode CPU power running WordPress on the Linode 512.
Not trying to belittle your site, but I hope you really need that plugin before you go tearing your hair out like I see a lot of people doing with WordPress. You did the right thing moving to Linode + Nginx

I'm just guessing but now I think you can relax about speed. If you're new to Linode--just see what your new Linode can do without this cache plugin, you should be pleasantly surprised.
In my experience, if a site is slow after moving to Linode, there's probably a serious flaw somewhere and the cache plugin only makes that harder to pinpoint and correct--the slowness is still there, but now only intermittently when the cache is reset.
Before installing a WordPress cache plugin I would try a simpler, more elegant solution--check your my.cnf settings. Install "mysqltuner" and follow the recommendations. Your experience may be different, but when I install MySQL with Fedora, by default the caching is not the best and you can see a huge improvement with very small my.cnf adjustments.