The problem is actually, more or less, building up the search index - this is only an issue the first time you do a particular kind of search, and it's fast after that. This involves parsing all the source code, which is a recursive process, which FF doesn't optimize (whereas Safari and Chrome zip through it much faster).
It's probably the DOM manipulation specifically. Are you adding the results in one big innerHTML assignment?
You can also try breaking the search into small chunks with setTimeouts between them.