I know much of this thread is old, but I never saw a mention about what the purpose of the website was.
Business? Personal blog?
Text only, or graphics-intense?
Simple personal stuff can go on wordpress.com (NOT wordpress.org).
If your running a business site with Wordpress, you obviously won't want the cheapest provider.
Currently, I run 3 websites and they're all hosted at a Wordpress-specific hoster. Way back in the day we started with Network Solutions and that was a cluster. We got hacked (very possibly through NSI) and they a) never admitted it b) didn't do anything to help and c) didn't know how to help in any case.
We moved to someone who only hosts Wordpress installations and the difference is night and day. The site is rocket-fast now, and they pointed me to CloudFlare as another performance and security measure.