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