I use Host Virtual (vr.org), which has a variety of root-access plans. I'm very happy with them. Their tech support is fast and helpful. They may not always have the answers for highly specialized things and specific software (like running a radio station), but anything having to do with running a basic server, they will do all they can.

In any case, since there are cheap virtual private hosting services with root access, you really want to go with that, rather than shared hosting, which gets annoying real fast when you know what you need to do.