I can top this problem: For me firefox startup takes 90 seconds, because several calls to getHostName() take 12 seconds each.
The problem seems to be that selenium creates an INetAddress (selenium class) for each java.net.InetAddress found on each network interface.
The INetAddress constructor immediately calls getHostName() which does a reverse lookup.
The irony is that the retrieved host name isn't normally used (only in some error diagnostics it seems).
I patched Selenium's INetAddress to store the java.net.InetAdress and only call getHostName() once when needed.
FF startup is down to 3 seconds now.
Any word from a selenium developer?