This site uses about 150 to 200 gigs of bandwith / month and about 2 gigs of space. But that also includes squad forums and the popularity of the site. I would say start small, 500 megs with 30gb of bandwith is a great place to start. You can always upgrade when needed.
If you have found a host with a good price and they offer what you need + the support then give them a try. And always try to go for the host that offers a money back quarrentee. Otherwise you could end up paying for some bullcrap host for a few months.
Here are some hosts:
www.eryxma.com
www.liquidweb.com
www.hostrocket.com
Our current host is
www.rackshack.net . Completly unmanaged so they don't offer any support.