Dedicated Server - Where are Thou?

I'm looking for a dedicated server to host the ebiz I'm working with.
Besides the normal things such as high bandwidth/traffic allowance, good service and around 10g storagespace we're also looking for a host that will give us root access to perform our own installations.

If you have knowlegde about a company that is excellent at this dedicated servers then we would like to hear from you.

Furthermore - having a look at http://www.cihost.com/ they look quote impressing, but i've read that they some time ago had ALOT of trought with their uptime. Anyone here still with them and know how it has been since?

thanks.