What's an alternative to "Everything" search for Linux?

If you're just looking for file names, locate is pretty standard on Linux systems, although your distro might not have it installed by default.

$ locate vmlinuz
/vmlinuz
/vmlinuz.old
/boot/vmlinuz-2.6.35-28-generic
/boot/vmlinuz-2.6.35-30-generic

locate relies on a database of existing files which is normally updated nightly by a cron job, so its results are more-or-less instant.

If you need up-to-the-second results, you can instead use find, but it will take a while because it goes through the filesystem reading and examining every file present.

$ find / -name \*vmlinuz\*

will eventually return the same results, plus many "permission denied" errors if you're not running it as root. Note that the first argument to find is the directory to look in (including subdirectories), so you can limit it to only a part of the filesystem to speed things up considerably if you have some idea of where the target file(s) might be.