Most of the major factors have been covered here, I would just add the following.
I have gone through quite a few ISP's over the years, mainly attracted by low price, IMHO you do get what you pay for.
I had a very low cost host that offered unlimited bandwidth etc, unfortunately there architecture was not sufficient to supply unlimited bandwidth to all the customers they had got with the low prices. The result was timeouts when pinging the server 25% loss!!!
Couple of things to take into consideration with any host
* Network they have in place - Dual/Quad backbone to separated suppliers
* The connection your box has to the network
* Spec of your server
* Most important the level of support the host offers, IMHO this is where most fall down. Don't touch a host who only replies by e-mail, also I have found for me its best to have a host of the same time line, as they will have limited phone support out of hours. ( I am in UK)
Also you will find a lot of "Dedicated Server" providers actually just buy/rent them from bigger company, or are operating as an affiliate. If you were to search for a dedicated server host its difficult to know who actually owns the servers and who doesn't!
Some of the other posts here gives personal experience, which is a great point of reference.
Also by careful when going to comparison site as some of these are on an affilate basis and can be biased.
I am not trying to promote any given host here, just some points to look out for.
Good Luck
Steve