Database Performance Tuning
A good starting point is the MySQL Slow Query Log instead of the general query log. You can set the 

You'll want to log queries that aren't using indexes

Update
In your question, you state that the system is 'nice and responsive' over local network, but that you haven't done any performance tuning. The slow query log I pointed out will help you identify queries that are taking a long time to run (over 1 second, if configured that way). IMO, this is a great starting point. 
The longer a query takes, it is much worse when the response has to be transmitted over a WAN.

One tool I've recently discovered is mk-tcp-model that analyzes output from tcpdump to help measure how long a request takes to respond. You can see how many request/responses are coming in and how long each takes. The best tuning over a WAN is to reduce the amount of requests you need to make.