Start small. Shared hosting is probably fine unless you need the features of a dedicated Virtual Private Server. Some things that used to require dedicated VPS can now be outsourced to services like Amazon S3 and MySQL hosting.
Shared Hosting:
I like Dreamhost.com for all my PHP/MySQL related sites. They offer SSH accounts, unlimited number of domains for a shared hosting account, IMAP and preconfigured webmail, cron and a bunch of other goodies. Support is decent but not great. Using the promo code "JMK" will get you $50 off if you sign up. They are already very cost effective for what you get, with or without the promo code.
VPS:
Don't go with dedicated hardware, choose a VPS. I really like the service provided by MediaTemple.net. Their knowledgebase and support staff are top notch and their prices are reasonable. If and when you grow to need multiple servers they can set you up with your own private network. They do not charge for traffic between these machines which can save you alot of money. Do not go this route unless you are comfortable with linux administration. You will be responsible for maintaince of the machine.
General Tips:
Use a different registrar than your hosting company. This ensures that they don't give you the run around if you ever need to switch hosts. I foolishly used Network Solutions several years ago and when I went to change hosts that continually hung up on me on the phone, didn't answer my emails, and eventually let me domain name expire, at which point they said they could get it back for around $200 instead of the already inflated normal price of $25 to renew.
Use a version control system for you code and keep your own regular backup of your site. You can setup a cron job to run daily / weekly backups of important data and have them sent to another hosting provider or online storage. Check them occasionally and make sure they contain all the right data.