I'd second the recommendation for Lexiconn. We hosted with another company for a couple of years, then switched to Lexiconn just about two years ago after one too many extended downtimes.
Lexiconn guys are pro's, at hosting, AND shopsite. And don't leave you guessing what's going on.
I no longer worry about host-caused downtime. Now it's just me who breaks things
-Chris