When people telnet to my machine, it lacks the login prompt, but is still
  ready to receive their username.  Hitting return causes the login prompt to
  be printed.
  It appears the first one is not being sent.  Why?

Because of post-4.3 telnet options negotiations? I'm finding some xterm
local clients here (thats local on the xterminal) negotiate line-mode
and echo passwd en claire and from OSF/1 telnet has the local username
stuffed into the pipe and NetBSD just asks for a passwd like rlogin.

Not complaining, well maybe a little about passwd echo, but thats down
to motherhood of older telnet option negs if I understand the issue right.
(which I doubt...)

-George