The Total PHP site has a few suggestions for you to look at before choosing your next web host - five of them:
- PHP 4 or 5? - if you haven't made the switch to PHP5, there's no better time
- Linux/Apache - Windows is largely an ASP.NET platform
- Access to outside the document root - it can be very useful for templates, config files and the like
- Scripting requirements - be sure anything you might need for an outside application (like WordPress) is there
- General advice
There's a bit more detail on each of the points to round out the advice.