Provavelmente, apenas assista a este vídeo:http://screencast.com/t/OWE1OWVkO Como você vê, o atraso entre uma conexão sendo iniciada (via telnet ou firefox) e meu programa primeiro recebendo a notícia.

Aqui está o código que aguarda a conexão

    public IDLServer(System.Net.IPAddress addr,int port)
    {
        Listener = new TcpListener(addr, port);

        Listener.Server.NoDelay = true;//I added this just for testing, it has no impact

        Listener.Start();

        ConnectionThread = new Thread(ConnectionListener);
        ConnectionThread.Start();


    }

    private void ConnectionListener()
    {
        while (Running)
        {
            while (Listener.Pending() == false) { System.Threading.Thread.Sleep(1); }//this is the part with the lag
            Console.WriteLine("Client available");//from this point on everything runs perfectly fast 
            TcpClient cl = Listener.AcceptTcpClient(); 

            Thread proct = new Thread(new ParameterizedThreadStart(InstanceHandler));
            proct.Start(cl);


        }

    }

(Estava com problemas para inserir o código em um bloco de código)

Eu tentei algumas coisas diferentes, poderia estar usando TcpClient / Listener em vez de um objeto Socket bruto? Não é uma sobrecarga obrigatória de TCP, eu sei, e tentei executar tudo no mesmo encadeamento, etc.