I posted links to two datacenters where I have servers.
I also had a server with RackSpace and it was a terrible experience, costing me DAYS of downtime and hundreds of thousands of lost visitors. Really.
ev1 has been a fantastic experience, as has The Planet.
These are not 'budget' datacenters, the prices are average, if not slightly expensive once you get a fewupgrades, such as a hardware firewall, upgraded memory, or additional hard disks.
How do you decide? Good question.
Take the advice people give you, plus do your own research, contact the companies, and see what the best scenario is for your situation.
What I recommend is get an unmanaged server & an outsourced tech to work for you, someone you can consult when you have something thats beyond the scope of your talent. This way, you have your server, and you have a tech that knows it inside and out. With rackspace, you get whoever is on the clock. This can cause problems. Then you get into the he-said-she-said situations when the server is down and nobody can fix it and puts the blame on all the other techs. That's what happened to me and I was furious. My account manager ripped up the contract I had signed committing to a year of service, and let me go find a new host with no penalty. They're lucky I didn't sue, but there was really no case considering the disclaimers involved, so that would have been a big waste of time anyway.
I wouldn't wish anyone I know (or have seen around on this board) to have a server at rackspace. Unless you like pulling hair.