In which part of the world?

USA,  West Coast

I'd recommend going with a linux host if you can. It's cheaper in most cases. Linode gives you 100 dollars free credit to try it out. But you need to open a ticket to get port 25 opened. 

Parkside Technology might be a good bet, they're west coast. There are quite a few others in and around the community that will chime in at some point as well I'm sure. That said - as Zach pointed out - getting a cheap Linux host with a solid cloud provider and having a good administrator set it up properly is also a great option.