The biggest difference would be that free hosts wont give you your own domain
Agree. Most of free hosts don't have your own domain. The advantage of free host is you can save your money but limited on space. while of paid one, more space and you can do what you want in your site.
Paid webhosting is better - no doubts about it - but it doesn't mean that works always well. Remember rule - money talks - and check how many websites and databases is attached to your server, may that is why your web is not server properly even if your website is on paid service. Plus some providers can have strange ideas and ask you for extra money months before contract is off etc.
Maybe a free web hosting company put an advertising on your site which is negatively but it's not the really problem! The really problem is in the name of the used domain. If you are on a free host the name of your website will be depend on the name of your free host company. What's happening when this company going to have a name changing? In this case the works with your webmarketing would be waste of time . . .
The Domain issue is going to be across the board (except with microsoft office live, but they force you to use their templates). But uptime isn't so cut-and-dry. A lot of small web-hosts really aren't good, if you pay for hosting by some guy running a server in his livingroom up-time could be a lot worse than a reputable web-hosting company that offers a free, ad supported, option on the same servers.
When it comes right down to it, if you're actually worried about PR then you must be dealing with a business. In which case the $100 a year for a basic web-hosting plan is well worth the money.
On the other hand, if you were just wanting to post a personal site with some pictures of your cats and a Blog, free would be fine.
There are certain things that no free hosts offer. I agree that things like uptime, site speed, and ugly templates depend on the host. But at BEST you'll get to either use your own site code OR have your own domain (only microsoft, as far as I know). Free hosts make money by getting free publicity from you. If they can't at least put their advertisement on your site they're just giving away a very expensive product... and that company just doesn't exist.
With a free host you will ALWAYS have some form of advertisement for them, either a forced banner at the top/side of a page you design or something worked into a template they gave you to work with. It's just how free hosts work.