DigitalOcean is killing it against Linode - I just migrated my last services off Linode because you still cannot attach arbitrary sized disks to your instances, something they've been promising as arriving "soon" for months. Go DO!
We occasionally experience problems with %steal due to other VMs in the same host. It was a lot worse when we had a critical service hosted in Linode, but that was gutted and moved to actual hardware. Only a small, low-traffic bit still remains in Linode.
What kind of issues are you running into? There's a lot of issues that can happen on a server, but a lot of them are due to not enough resources or a misconfiguration.
Now, if your server is seeing constant issues on the host your server is on...