I did something similar to use images in a mosaic, and taking the image contents into consideration. This turns out is super-simple as long as you do everything in JPEG space: Just use however many coefficients to compare! So, scale the original image to have 8x8 pixels per "image pixel" in the final output, and then scale every candidate to 8x8. Now just compare the DCT coeffs directly!

A similar technique could probably be used here.