Personally I prefer a paid service, as you get more features, more control, and better support if there's issues.
I've been using this hosting service, and re-selling it to my customers for several years now and I am very happy with it:
http://www.christianwebhost.com/index.html
The "A" package offers everything you'll need, for a long time, plus you can run a second site underneath the main one for free - "parking" it so it looks like its own complete site. So say a business site then a gaming site. Pleanty of disk space to upload music files, use streaming to play samples for your customers, etc. Lots of bells and whistles...
LGen. Hamilton
II Corps
ANV, CSA