Strange, I've never found Spotlight to be that slow or frustrating. I just tried it again to be sure I wasn't kidding myself, and find that I type about 3 keys, and then there's the app I want by the time I'm finished pressing the 3rd key.
But that might be because my .Spotlight folder is > 1 gigabyte. And that's smaller than it has been in the past - my previous hard drive had it larger than 2 gb if I remember correctly, because I had tweaked it to index my source code. On my wife's computer it's only about 400 meg, and it finds applications in about a second (still much slower than Alfred or Quicksilver).
Definitely depends on your usage patterns :)