I'd start with a VPS (which I'd then change to a backup MX later on). If you have a control panel like DirectAdmin it'd make creating accounts etc very easy. When you do go to a dedi, I'd probably look at a core2duo with lots of RAM and some quick SATA hard drives in RAID10

myriadnetwork.com will be a really good choice for VPS, they offer both cpanel and DA
valuhost.com offers Dual Core series managed dedi,
one more host to consider is ahosting.biz, they have promotional dedi plan starting with $60.

A2hosting.com with their morden sollutions have good prices there. I personaly like their wide choise of different packages.

I would do some more market research if i were you as the vps plans offered by a2hosting are not that amazing. I know a number of places where you could get a higher spec VPS for the same price.