Hi Lucas,
I have a few preferred hosting companies, but I'm always keeping my eye out on the Whirlpool Forums on Web Hosting:
http://forums.whirlpool.net.au/forum/116 as they are a mine of good information about hosting companies, with regular and up-to-date feedback. You can see which ones are troublesome, which ones respond to issues, and hear peoples experiences using different providers. (Don't forget to factor in that some people are just never happy!)
When looking at new hosting packages, always check it meets the Revo server requirements page (
http://modx.com/revolution/developer/requirements/ and if in any doubt whether the package can meet these requirements, just email them. If your package can meet the minimum requirements, then you shouldn't have a problem with your traffic at all. 500MB RAM is ok for a webserver on a VPS, but if you get busy, you could find its not enough. Just make sure you can upgrade/add more.
My own experience in over 10 years of building websites has shown that good hosting companies can go bad, and bad can very occasionally become good, but of the good ones, only a few stay that way for a long time - so it pays to do your research as much as possible. Personally, I've been enjoying the hosting of VentraIP a lot lately, and also Netlogistics. But don't take my word for it - read the forums and get other peoples opinions too!