Hmm, seems a bit odd. Is the query returning quite a lot of features and fields? Maybe the response comes quickly, but the parsing and everything that takes place before it is complete is taking some time? Maybe limit the amount of fields you are returning if you haven't done so already? Also, are you running in release or debug? If debug, I would be curious to see if release is faster.
Also, depending on what you are doing (not sure if this fits into your workflow or not), have you considered doing a local query on the GeodatabaseFeatureServiceTable? These run client side and should be quite fast.
-Luke