The color issues are challenging, but the scaling issues are tough as well.
Given you know you want to print it at about 40" across (let's say 40"x40" for the sake of discussion), what size (printed) does each individual image of the mosaic need to be in order to be discernable at close range? And what is the desired viewing distance for the entire printed mosaic? This may also influence the size of the individual photos.
Let's say the smallest an image can be while still being discernable at close range is 1"x1". This would mean that a 40"x40" mosaic would only be made of 40 images in each dimension, which means it can only be used to represent an image that is 40x40 pixels, which is a very small number of pixels for any image.
If you make the individual images 1/2"x1/2", you still only have 80x80 images making up the mosaic. To get an idea of whether 80x80 is enough, scale a square digital image down to 80x80 pixels and view it at 100%. I think you will find that is barely enough detail.
If you printed that 80x80 pixel image at 40"x40", how far away would you need to be standing before it is recognizable as the original image? Probably about 80 times the distance you are from your computer screen (where the 80x80 pixel images is probably approximately 1"). If your eyes are 1 foot away from the computer screen, that means you would need to be 80 feet from the printed mosaic to get a similar impression of the image.
But again, at this point, we are talking about individual images that are only 1/2"x1/2". Are these even big enough to be discernible? I'm guessing probably not. So, I have a feeling that a 40" printing simply will not work. Therefore, I recommend working out the scaling issues first.
Experiment with printing an individual image at small sizes to determine what size is discernible up close, and then think about how many tiles of a mosaic would be needed at that size in order to make the composite image recognizable by working with it on your screen to see how many pixels are needed to give it adequate detail. Then multiply the number of pixels by the print size of the mosaic tiles, and you'll know how big your entire print will need to be, and whether the project is even doable. If it is, then at least you have some parameters to work with in whatever mosaic making software you choose.
I hope this helps and that you get it to work out!
BTW-- I have used MacOSaiX and found it worked well, though when I tried to significantly increase the detail of the tiles it became sluggish and ultimately failed. I don't blame it, I was asking it to do a lot, and it is limited by the computer hardware.