Doing searches from the Google Search app can be strangely slow on many devices, but the cause isn't obvious. The community might have figured it out, though. If you're sick of watching the Google Search app chug along on Android, this might fix you right up.
The cause is alleged to be the Search Applications Provider in Android, which returns a list of installed apps on the device to build suggestions. To take care of the issue, you have to disable that app. Go into your settings to Apps > All > Search Applications Provider. Disable the app, and you're done.
The Search Applications Provider might simply be poorly optimized. A bug has been submitted to the issue tracker, but JBQ (the manager of AOSP) is currently unconvinced it's an AOSP issue. There is a thread on Reddit with tons of users reporting success with this, but that doesn't prove anything. It could still be some sort of placebo-fuelled mass delusion. However, it seems to work for us. Some people are reporting problems with searches after attempting this, so definitely proceed at your own risk.