What data should I use to test an FFT implementation, and what accuracy should I expect?
If you want to verify an FFT algorithm for correctness, in the sense that it performs the desired function that has the known properties of the discrete Fourier transform, then you can use the approach proposed in:


  Ergün, Funda. (1995, June). Testing multivariate linear functions: Overcoming the generator bottleneck. In Proc. Twenty-Seventh Ann. ACM Symp. Theory of Computing. (p. 407–416).


The above paper is referenced by the makers of FFTW as their method of choice for verifying that a particular FFT implementation does what it should. The proposed technique distills the function into three main components that are verified with separate tests:


Linearity: The DFT (along with its other cousin transforms in the Fourier family) is a linear operator, so for all values of $a_1, a_2, x_1[n], x_2[n]$, the following equation must hold:


$$
\mathrm{FFT}(a_1 x_1[n] + a_2 x_2[n]) = a_1\mathrm{FFT}(x_1[n]) + a_2\mathrm{FFT}(x_2[n]) 
$$


DFT of the unit impulse: A time-domain signal equal to the Kronecker delta function is applied to the input of the FFT algorithm and the output is checked against the known DFT of the unit impulse function (it transforms to a constant value in all output bins). If the FFT algorithm provides an IFFT, it can be tested in reverse to show that it yields the unit impulse function again.
Time shift: Two sets of data are applied to the input of the FFT algorithm; the only difference between the two in the time domain is a constant time shift. Based on the known properties of the DFT, this should effect a known linear phase shift between the two signals' frequency domain representations, where the slope of the phase shift is proportional to the time shift.


The authors of the paper assert that these tests are sufficient to validate the correctness of an FFT implementation. I've not used this technique in the past, but it does seem to make sense, and I would trust FFTW's authors (who have produced a great piece of free software) as credible authorities on good approaches to the validation problem.