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 *************, 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.