What you are trying to do has been tried over and over by hundreds of researchers and there is quite a large body of work about this. Check the proceedings of the ISMIR conference. Even if it is not up to date, read Elias Pampalk's thesis : http://www.ofai.at/~elias.pampalk/publications/pampalk06thesis.pdf

To quickly orient you on the right track:

Music can be similar according to many dimensions: a) timbre/texture/genre ; b) rhythmic pattern ; c) melody/chord progression... and more! From your message it's not clear what you want to measure!

• If you are interested in a) the features you might want to look at are MFCC (Mel Frequency Cepstrum Coefficients), since they somehow capture the way human hearing works (frequency warping, log scale) and since they are decorrelated (making modeling easier).
• If you are interested in b), look at a feature called "Fluctuation Patterns" (Pampalk, in short autocorrelation of the signal in the 0.1 .. 10 Hz range over a few bands) ; or Whitman's "Penny" features (FFT of the MFCC along the time axis).
• If you are interested in c), look at chromagrams. Start with Ellis' chromagram code (http://labrosa.ee.columbia.edu/matlab/chroma-ansyn/) then move up to Mauch's implementation if you need something more robust (http://isophonics.net/nnls-chroma).

Computing pairwise differences between sequences is not very smart - eg: comparing a song and the same song offset by some silence will yield a difference while it is exactly the same! Not good. You'd rather compare the distribution of those features ; for example compute the mean / standard deviation of the features over song A and the mean / standard deviation of the features over song B and then take a probabilistic distance (KL, Bhattacharyya over those).

Finally, tempo detection is an entirely different matter. Best performance / accessibility paper on the topic is Ellis' Beat Tracking by Dynamic Programming. http://www.ee.columbia.edu/~dpwe/pubs/Ellis07-beattrack.pdf . It's incredibly simple but is close to state of the art algorithms.

What you are trying to do has been tried over and over by hundreds of researchers and there is quite a large body of work about this. Check the proceedings of the ISMIR conference. Even if it is not up to date, read Elias Pampalk's thesis : http://www.ofai.at/~elias.pampalk/publications/pampalk06thesis.pdf

To quickly orient you on the right track:

Music can be similar according to many dimensions: a) timbre/texture/genre ; b) rhythmic pattern ; c) melody/chord progression... and more! From your message it's not clear what you want to measure!

• If you are interested in a) the features you might want to look at are MFCC (Mel Frequency Cepstrum Coefficients), since they somehow capture the way human hearing works (frequency warping, log scale), since they are decorrelated (making modeling easier), and since they have lower dimensionality (13 coefficients vs 2048).
• If you are interested in b), look at a feature called "Fluctuation Patterns" (Pampalk, in short autocorrelation of the signal in the 0.1 .. 10 Hz range over a few bands) ; or Whitman's "Penny" features (FFT of the MFCC along the time axis).
• If you are interested in c), look at chromagrams. Start with Ellis' chromagram code (http://labrosa.ee.columbia.edu/matlab/chroma-ansyn/) then move up to Mauch's implementation if you need something more robust (http://isophonics.net/nnls-chroma).

That's for the features. Now you'll have to think of a better way to compare your songs once they have been represented as a sequence of those features. Computing pairwise differences between sequences is not very smart - eg: comparing a song and the same song offset by some silence will yield a difference while it is exactly the same! You'd rather compare the distribution of those features ; for example compute the mean / standard deviation of the features over song A and the mean / standard deviation of the features over song B and then take a probabilistic distance (KL, Bhattacharyya over those).

Last point, but which will matter later: computing the distance between a song and the rest of the corpus to find the nearest matches is quite inefficient. When dealing with large collections, techniques like LSH or Ball trees allow such nearest neighbors queries to be performed without explicit comparison with the whole corpus.

As an aside, tempo detection is an entirely different matter. If you want to look into it, best performance / accessibility paper on the topic is Ellis' Beat Tracking by Dynamic Programming. http://www.ee.columbia.edu/~dpwe/pubs/Ellis07-beattrack.pdf . It's incredibly simple but is close to state of the art algorithms.