I don't know about GUI tools, but:

Everything is so fast because it uses the index built into NTFS to find files by filename quickly, and NTFS is the definitive file system on Windows so it works everywhere.

On Linux, there isn't really an index built into the filesystem - some might have that, but I don't know about it. That said, plocate is a common tool that uses its own index. You have to update the database when files change (you'll probably have a job doing that daily), but searching the index is very fast.