In dealing with various clients over the past few years, I constantly find myself dealing with hosting packages that just don't work.  Rather, they take far too much effort to get to work! 

At base, Joomla's pretty simple to get up and running; it just requires three prime things - Register Globals and Safe Mode should be OFF and Magic Quotes should be ON.  Now, most of you out there likely signed up with a web host because of cheap prices - back when perhaps you just needed a domain and some email address, maybe a couple of static HTML pages as well.  That cheap host might offer these settings to help you run a Joomla site but that's just not enough.

The beauty of a CMS or Online Application Toolkit like Joomla or Drupal lies in the functional scalability they offer - you'll want to be able to grow your site in time but your hosting package could seriously cause headaches at those growth stages, requiring more effort than is necessary.  Its really worth shopping around for a host that will be there to support you along the growth path your site takes in the future.

Things I suggest looking out for:

• The ability to maintain your own php.ini (so you can set your own maximum file size for uploads, amongst other things),
• A package that scales in hard disk *and* other system resources with time,
• Shell access & ftp access to your server,
  
• Previous experience hosting Joomla and other Open Source php/mysql CMS' - ask the host to give you a few URLs to sites they host

Remember, its never too late to bite the bullet and spend 2 days switching over to a new host .  if you need help, head over to the joomla forums to look for pros who can do it or offer advice.