Most of my users access their accounts from outside the router (my network is based in my apartment and my wife and I are the only ones who use it here.) I don't users telnetting in because of the security risk (I don't quite understand this, but I've read about it in more than one place, so it's probably true), so I've enabled ssh so that they can log in and change their passwords if need be.
The issue here is trust in your "local" users, not ssh itself. Many of the recent vulnerabilities in the Linux kernel and other packages require that the attacker be logged in with shell access. If you don't provide shell access, you can afford to ignore these kinds of vulnerabilities and reduce the frequency that you patch the server. If you have untrusted shell users then you need to be much more vigilant, because they can use those vulnerabilities to escalate their privilege and root your box.
I use a hosting service that allows ssh, but as a matter of policy they require that the user submit picture ID before enabling this access. It's a hassle but I can understand this paranoia, as I operate servers myself.
You should never use telnet on a public interface. It exposes passwords in clear text, and that means malicious sniffers could get a shell on your box using the accounts of your trusted users. But ssh is not a panacea. Like https (secure http), it protects your users, not the server itself.
