Sounds like you'll have to divide the base image into blocks and apply your "average color" script to each one, because if you "duplicated" the base image pixel-by-pixel, the output image would have to be huge in order to see the detail of each of the small images that create the mosiac.
And how will you find which images already on the server are the closest match to the color you need?
And what if the base image has a large area of the same color? Will the same small image be used for the whole area?
Will the output be a single image with all the small images imagecopy()ed into it?
IMO, the average color script doesn't sound like "one of the two hardest bits"