I just signed up with Bluehost yesterday. It was a basic package (6.95/month for 2 yrs) just for a personal website. It said that it would take 1 to 2 business days to get my actual domain working for my site. But at around 6pm MT, they called me up, and confirmed my purchase, and got my domain working on the day that I bought it.
There's also Dreamhost, however I've heard that they have had issues with servers being down.
I'm not sure about hosts that can cater for a small company.
__________________
|