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.