I use 2 512Mb Linodes. One for nginx/PHP, one for MySQL. Putting these on different servers is by far the biggest leap in performance I ever got.

Monthly cost is about $40 ... unless you count my time.