upvote for linode, I'm using them for my personal server for over a year and I'm very satisfied.

They have an API for which you have documentation, stackscripts and other goodies, try it out.

You can go with slicehost as well, although I haven't tried them.