When I telnet to my netbsd box, from a sun, I get the above output from
   things.  This has only happened to me since I switched from 'rc' to
   'pdksh'.  It always happened when su'd, so I assume some shells are more
   likely to have this problem than others.

it has to do with line moded-ness.  basically, shells that don't do
line-editing, won't have the problem.
   
   Is there any non-botchy way to make this go away?  A stty kluge, or
   something?  I've heard rumors telnetd -k may fix it, but I'd prefer to
   avoid that, as I have perfectly respectable telnet clients everywhere except
   work.

telnetd -k will `fix' it, and that's what i use personally.  the
problem here is that it's a kludge, and sometimes when telneting
you won't get a `login:' prompt.  well, it won't get displayed, but
it is there -- you can type your username, and you'll get a password
prompt.

i'd go with jfw's suggestion of port 22, or get the telnet from
ftp.cray.com and compile that.

.mrg.