High bandwidth allowances on both the web and email, flexable email management with a master account that all incoming mail is automatically forwarded to. If you can find one that allows IP and domain blocking on the email side, go with that. Once you establich a business email account, the spam really starts flowing and you're stuck with it cause you don't want to change a business email address. Don't focus too much on the cost of the service, cause it'll still be the lowest recurring cost your business has, and the best return on your advertising dollar.
Don't forget to register all the possible variations on your domain, and have them all parked on your main IP. So you also want to look for a service that'll do that for little or no charge.