I've had good luck with Intermedia.net They are a little more expensive than some of the cheap-o providers, but I've had, I think 100% uptime for years. I'm also running two client's applications on the server, as well as my own web site.

They offer both Microsoft + Frontpage (yuck) with Access and SQL-Server databases, or Linux servers with LAMP. They also have things like SharePoint, Exchange, great web statistics, you name it.

Recommended.