Bryan Kennedy has a great write up to help you get it set up and locked down: http://plusbryan.com/my-first-5-minutes-on-a-server-or-essen...
We put our own twist on it which improves on his base (mostly security related): https://github.com/codelittinc/incubator-resources/blob/mast...
PS: We've been facing issues with certain regions of late, but the team is fairly responsive and helpful with getting fixes through.
Do you know anyone that is familiar with setting up VM's or managing servers? If so, hit them up and get them to set you up a linode vm (or whatever other provider you want) with nginx. If you don't, perhaps looking at getting a contractor to set you up.
Your problem might not be your host (thought Godaddy is unlikely to be good), as much as a lack of caching on whatever website software you're using (WP?).
P.S I've been using Digitalocean for about 19months now. (edit)
(not affiliated in any way, just a happy customer)
The things that most annoy me about digital ocean (No S3 like thing, no way to change your ratio of CPU to Memory to Disk) seem the same.
Edit - Noticed the giant hard drive instances. Super interesting. That could be enough to make me flip.