A C Zoom

Any of the dreamhost or site5 would fit the bill.

I have been using site5 for last 3 years. If you prepay 2 years in advance, you get $5/month plan and it gets renewed to the same price every 2 years. The management of site5 changed last year and it has been great since then, if you see their support forums, you will see their top guys (CEO/CTO) frequently lurking there and taking note of problems. They have a firewall (outbound as well), but you can ask support to open ports if you need (e.g. git remote)

--Amit