Anybody know how the performance (speed) of the FFT routines in Numerical Recipes compares to other free FFT routines? I've heard that the NR routines are S-L-O-W...

Yes, basically you are right. Like other NR routines, the FFT routines are not designed to push the performance envelope so much as to be clear, compact illustrations of the underlying mathematical ideas explained in the text. When you are ready to "graduate" to using higher-performance code, you should definitely do so! Of course, for many users with small or medium-scale problems, compute time is not an issue and the NR routines are just fine.

A good source of performance data, with links to FFT routines that are faster than NR's, is at http://www.fftw.org/index.html and http://www.fftw.org/links.html .

(If you read the source code for the fastest programs, you'll see why they are not suitable for direct inclusion in a text like NR -- how many pages of source code do you think the reader is willing to study at one sitting? :( )

Another interesting link is http://momonga.t.u-tokyo.ac.jp/~ooura/fftbmk.html