DigitalOcean, it's not shared hosting and therefore harder to configure, that being said it's definitely worth it. I've found that even on a low-end VPS you can juice it for more than you could with a high-end shared hosting account.
I use WP Super Cache, it's seen me safely through HN frontpages, popular reddit submissions and being linked from xkcd's blog.