Remote connection to MySQL server takes very long
Solution 1:
Probably you're lagging on an attempt to retrieve and verify reverse DNS of the connecting host. You can test this by turning on skip_name_resolve in the server's my.cnf, [mysqld] section.
If it is in fact the case (demonstrated by that parameter eliminating the delay), then you can solve the problem by either setting up DNS properly (forward and reverse) for the client, or by running with skip_name_resolve all the time (which means you can't use hostnames in your GRANT tables).