Avoid EasyCGI at all costs. They are under new management and were a nightmare during the transition.
When I went through that, the following thread generated some good discussion:
Web Host with ASP/PHP/MySQL w/ external access? - Front Office Football Central
I am currently with LiquidWeb, which has been pretty good. I know Ben has been happy with his host, and there are some other good suggestions in that thread.