The symptom: there is a long delay between the time the TCP connection is established and the time when the client software asks for a password (or, in telnet(1)'s case, when a login prompt appears).
The problem: more likely than not, the delay is caused by the server software trying to resolve the client's IP address into a hostname. Many servers, including the Telnet and SSH servers that come with FreeBSD, do this in order to, among other things, store the hostname in a log file for future reference by the administrator.
The remedy: if the problem occurs whenever you connect from your computer (the client) to any server, the problem is with the client; likewise, if the problem only occurs when someone connects to your computer (the server) the problem is with the server.
If the problem is with the client, the only remedy is to fix the DNS so the server can resolve it. If this is on a local network, consider it a server problem and keep reading; conversely, if this is on the global Internet, you will most likely need to contact your ISP and ask them to fix it for you.
If the problem is with the server, and this is on a local network, you need to configure the server to be able to resolve address-to-hostname queries for your local address range. See the hosts(5) and named(8) manual pages for more information. If this is on the global Internet, the problem may be that your server's resolver is not functioning correctly. To check, try to look up another host--say, www.yahoo.com. If it does not work, that is your problem.