My experience, which seems to be shared by just about anyone who has published benchmarks, is that Linode is appropriately conservative on the degree to which they oversell CPU, because generally, it appears that a task that wants 100% of four cores does in fact get close to 100% of four cores.
The only thing to look out for is that there is quite a difference in single threaded performance between their newer hardware and their older hardware. Our app is written in one of the popular interpreted dynamic languages. Generic benchmarks for that language showeda 2-3x difference on some tests when run on the different hardware, and our app showed similar differences on CPU bound tasks.
There are a few implications of this:
First, it complicates things when you try to make your staging environment mirror production. The quick check is to look at /proc/cpuinfo and see if clock,cache and model line up. If not, open a ticket and ask them to migrate instances so things match.
Second, while they try to size things appropriately so that your guaranteed CPU Is the same, regardless of which generation of host you are on, your peak CPU is going to vary dramatically since you get 4 cores, irregardless.
Most VPS providers I have come across dont like it if you start working out the millionth digit of Pi, but sometimes you have a task that takes a while and you can't run offsite.