20 seconds is completely outside of my experience. You were searching with the gmail frontend, or via IMAP? I have 5GB in Gmail and I get instant results as I type in the search box, and full results in about one second when I hit the enter key. I only have a little bit of email in my fastmail account so I can't really compare it.
This was with the Gmail front-end. It's entirely possible there was just something messed up with my account. I haven't come across too many others that have had similar issues, but most people I know have much smaller accounts.
Thanks for letting me know my info is out-of-date. The problem with these sorts of comparisons is it's hard to use both options extensively, simultaneously.