Whatever you do, avoid companies that have large customer bases. Tech support is going to be slow, servers will be overloaded, and you're not going to get as much for your money as you could with a smaller host.
I'm using darkfiles.net right now, and they're decent. Two guys run it during the evenings after work, so there's usually no support response until that time. But when there is a problem, they work on it until it's fixed and usually credit me for that month if it's serious enough.
techm3 is hosting mp3car.com and I'll probably be moving my site as well as some of my customer's websites to him in the near future.