Koliko ja znam, boolean fulltext ne bi trebalo da automatski sortira rezultate po relevance, sto znaci da bi trebalo da radi jako brzo. Ja imam u jednoj firmi foto-arhivu sa 2M rekorda i to radi pristojno brzo...
znaci mora da bude problem ili sa necim drugim u upitu ili sa samom bazom (da je index prevelik, pa ne staje u memoriju)
Najbolji izvor informacija ti je mysql dokumentacija i stackoverflow.com
EDIT: Nama treba chat ovde, prebrzo idu odgovori
EDIT 2: probaj da koristis ORDER BY score, pa vidi jel onda brze...