I've setup a Win2k8 R2 RDS Gateway. It works great but the initial connection takes 10-20 seconds. I've had a hard time finding troubleshooting ideas for the problem. Anyone have any suggestions on where to start or common issues?
We had this problem and ended up virtualizing Remote Desktop Gateway on it's own VM under Hyper-V. We isolated it away from our other server functions, and it sped it up as far as connections go.
We recently installed a VPN (Remote Access Server role) for sstp traffic, and we noticed our VPN connection happens a bit quicker than the RDP one through SSL.
Our advice to you would be to build a box in a lab environment with only this service loaded and the appropriate certificate to see if something else is perhaps slowing it down.