I had some similar issues with a host earlier this year. I did quite a bit of research to find a new host. I decided to go with a VPS, and pared down my list of possible companies to liquidweb and knownhost.
liquidweb run "managed" vps setups, and knownhost run "semi-managed". I didn't have a lot of server experience so I almost went with liquidweb. But after PMing with one of the reps from knownhost on webhostingtalk, I decided to give them a try with one of my small sites.
The result is that they've been great. I've been with them for close to ten months now and their service is excellent. I've had no downtime that I'm aware of. Their response time to support tickets is so fast, it's amazing. And they've been patient with my newbie questions, walking me through things and at the same time offering to "do it" for me as well.
Recently, I moved my main site over to knownhost to the same VPS account as my smaller site and all is good.
If you're looking for a possible VPS host, they might be worth a look.
If you go with them, let me know how it works out for you.
-Chris