need tiles with the same or bigger size as the size of tiles in your
printed mosaic. If tiles in your printed mosaic will be 1 x 1 inch and
you will print it at 300DPI - you need your tiles to be no less than
300 x 300 pixels. You may use bigger tiles 400 x 400 or even 2000 x
2000 but not less than 300 x 300.
may just use large original 4 - 6 Megapixel photos. It will takes a
little longer time to save output mosaic in this case but - IMHO -
there should be not very long.
may downsample a very large photos to some middle sizes like 640x480 or
even 300 x 300, usually it is not necessary but in case of very large
libraries and mosaics it may speed up the process.
you may prepare a cropped photos: cut one large photo into few smaller
different pictures. It's good to get a large number of different tiles.
here for more info.