I have been googling around for something like Spotlight too (that's how I ended up here). That is certainly one of the best features from Mac OSX.
I'm actually very new to Linux, I'm just using Linux Mint 15 Cinammon for less than two months now.
The search function in the Linux Mint menu (which you can access by pressing "Windows button") also search as you type, as fast as Spotlight, but unfortunatelly only for applications included in the menu. You cannot search any document with it. It's pretty handy to find apps you need, at least that's what I experienced. For example, I need to type a document, but I don't know the app's name (considering I'm very new to Linux), I just search for "text", and the search result come with two apps, "gedit" and "LibreOffice Writer". "gedit" is something like notepad in Windows, and "LibreOffice Writer" is like Microsoft Word. That is something Spotlight does, isn't it?
Anyway, You can try installing "Recoll" to search for documents and its content. It's not as good to Mac OSX Spotlight, not even close, but I think that is the best option for now.
Btw, please let me know if you find something better than "Recoll".