First, check around, I have one I'll mention right below but always always always check around and get the best deal (not just in price either -- you've no doubt sworn off geocities and tripod because you really do get what you pay for). Hopefully some of the others on the board will say who they use and what it costs and how their own service has been. The below is personal experience which may or may not reflect everyone else's experience with this hoster so take everything below at your own risk.
I use Stargate for my website (http://www.stargateinc.com/us/hosting/index.asp). At the time I signed up, all they had on the cheap end was the Pro Plan ($9.95/month for which they now include free domain registration for as long as they do the hosting whch I don't get because I signed up prior grrr), now they have more plans available all the way down to $3.49. There are a lot of features I don't use (email accounts, got too many already) but I figure it is better to pay a little more for a little more than I need.
As far as reliability, it is pretty good until it goes down, when it does it is a doozy. After a rocky start (caused by a conflict in my FTP software and the inability of their tech to 'attain comensurability' with me) the service was glowing for about a year and a half. It went down then for nearly three weeks as they did an equipment shift, still a little raw about that -- actually some of you might remember me saying something about it because it was just after I did a major change on the plans at the site. After that grrr-period everything went smoothly up to today (just checked it and everything is hunky-dorey).
"If you haven't got anything nice to say about anybody, come sit next to me."
- Alice Roosevelt Longworth