I personally use one of those cheap, big hosting companies (Hostmonster) and haven't had a problem in 7 years, specifically for Wordpress.

I would say regardless of which brand, do pick a company that a) has longevity (not going to disappear in the next 2-3 years) b) has decent customer support.

You can try this out just by calling the numbers listed on each hosts' websites and seeing what the process is like to talk to a live human.