... I would have suggested RackSpace. We used them in a previous job and they are worth the money. However, at the time, they only fully supported RedHat. Debian was available, but they couldn't do as much for you (like RAIDed hardware). We also had hosts with a few other people and the support was distincly less than adequate.

Wade.