Bandwidth woes!

Eeek! I've just received a bill from my hosting company for exceeding my bandwidth quota for November. I've checked by web statistics, and it doesn't look as though anything's been slashdotted or instapundited, just the general upward trend in hits. It looks like this weblog has just outgrown my current hosting package.

This forces me to consider my options. Do I stick with the same provider and upgrade to the next level up in hosting plan, costing 50% more but giving me four times the bandwidth? Do I try and redesign the site to use less bandwidth by making the front page (which accounts for the majority of hits) smaller? Do I learn some google-fu to direct search engine hits away from the main page towards the much smaller individual archives instead?

Or should I change to a different host? My current provider had been hosting my homepage well before I started blogging; It's really geared towards small-scale e-commerce rather than as a blog host. Perhaps one of the specialised blog hosting companies might be a better bet?

Recommendations, anyone?