I suggest Explode Host.
http://www.explodehost.com. It is my company
. We do not offer free plans, but have good plans for inexpensive prices. We use P4 2.8s . If you want specs, you can PM me. We are proud of what we use, so we are not afraid to tell people. Hope this aids in your search.
-Eliav