After receiving the ClientHello message, the server is taking an exceptionally long time to respond with the ServerHello message. After that, the key exchange is pretty quick.
I would guess that something is up with the MTU of your server’s network interface, but it would take more information to be sure.
Some extra information could help:
Check if it is still slow if you connect over loopback interface (from the server):
time (echo "Q" | openssl s_client -debug -connect 127.0.0.1:443 -servername www.snowcrows.com)
Check MTU:
ip ad | grep mtu
Edit: Apparently Apache hitting the MaxClients limit can also manifest itself like this, try increasing that if it’s not already high.