i recommend lunarpages http://www.lunarpages.com. they don't offer telnet access (yet - it's supposed to be coming soon), but they have a host of other neat features (including a pretty low price) and their support team will install any modules that require compilation.

this is starting to sound like an advertisement, so i'll stop now...