Most hosts will NOT have telnet access, as it's insecure (plain text); however, most will give you SSH access (which is basically encrypted telnet).
Another reason to go a VPS route, you'll have root access to your VPS to accompany your dedicated resources