[TakeiT]

Nuclear Fallout Servers, it's all I've ever used. They have their own boxes (Not reselling), they offer linux/windows, with change between the two on the fly, have a good firewall system and excellent support.

However, you have to rent a full virtual server through them.