For vps offers check out
http://www.webhostingtalk.com/forumdisplay.php?f=104
I'd go for one with centos and cpanel. Cpanel will make it easier for you to mange but will only allow 7-9 emails a second due to it uses exim, if you want more you will need qmail as the smtp check out interworx.com. Cpanel is the most stable bet.
If you want a send, bounce, unsubscribe, comprehensive stats email broadcast program I'd use octeth
http://www.octeth.com/products/oempro/ we use it to broadcast emails for our clients HP, Toyota etc. Great product, great service and easy to use.
Dave