by locally.. do you mean connecting to a server on the same development machine? that will always be dramatically faster.
it sounds like you have either a design problem, or a server tuning problem, or possibly users with overly demanding requirements (and possibly a bit of all 3).
sounds dumb, but are you retrieving only the data the user requires (so there is no redudnant data pumped up and down the line), are you taking maximum advantage of the server to do its processing
have you checked the server loading.. does it need more memory, can you identify if there are queries which are clogging the server.. it may be reviewing the indexing strategy may help. forget if its show or explain on MySQL.