Strategies in reducing network delay from 500 milliseconds to 60-100 milliseconds

I may well be wrong, but personally I smell a rat. Your times aren't justified by your setup; I believe that your requests ought to run much faster.

If at all possible, generate a short query using curl and intercept it with tcpdump on both the client and the server.

It could be a bandwidth/concurrency problem on the hosting. Check out its diagnostic panel, or try estimating the traffic.

You can try and save a response query into a static file, then requesting that file (taking care as not to trigger the local browser cache...), to see whether the problem might be in processing the data (either server or client side).

Does this slowness affect every request, or only the autocomplete ones? If the latter, and no matter what nginx says, it might be some inefficiency/delay in recovering or formatting the autocompletion data for output.

Also, you can try and serve a static response bypassing nginx altogether, in case this is an issue with nginx (and for that matter: have you checked out nginx' error log?).

One approach I didn't see you mention is to use SSL sessions: you can add the following into your nginx conf to make sure that an SSL handshake (very expensive process) does not happen with every connection request:

ssl_session_cache shared:SSL:10m;ssl_session_timeout 10m;

See "HTTPS server optimizations" here:http://nginx.org/en/docs/http/configuring_https_servers.html

I would recommend using New Relic if you aren't already. It is possible that the server-side code you have could be the issue. If you think that might be the issue, there are quite a few free code profiling tools.