We're happy with our ServInt.com Virtual Private Server for our website (about 20 GB of traffic a month, 20 email addresses with around 250 messages a day, plus we run Kayako's eSupport help desk software).
Visit the
www.WebHostingTalk.com forums for lots of good info
www.SpamStopsHere.com for an excellent email filtering service that removes 99% of your spam before it even reaches your server, with 0 false positives if you turn off the optional spamcop.net blacklist filtering.
Don't pick a host just because they offer to submit your site to google, etc. since that's really a different service from hosting, and you should want your host to concrete on keeping your server up and accessible.
Nepotism plug: my brother runs a company that offers press release services, they can do more to raise your profile than the website submissions that everyone can do themselves:
www.Send2Press.com (I have no connection to his company)