How Do I Print Photos?

F-Spot can make some of the things you are asking for (though not all)

On the other hand, and though this is not an answer to your question, but eventually, and hopefully, it will be. There's a project called DarkTable, which is being developed as a substitute of Lightroom. The print interface, however, is still in the list of future features, but it's promising. More info: http://darktable.sourceforge.net/features.shtml

Edit:

What about gthumb?:

1. Up to 600 dpi
2. No standard sizes, but customizable ones
3. Paper tray selection in the print dialog (cups, I think)
4. Can do grids, but you can't mix grid sizes (you can mix photo sizes, but within the cell grid -meaning they will be adjusted to the cell size, but you can't select each image's size-)...
5. Guess you can print several times with same settings (you can't save settings, tho)
6. Can't test the borderless, as my printer is not capable of doing such a print :(. GThumb's dialog does allow you to set margins to 0, but I can't test it...

Try Geeqie, too...

1. Unlimited dpi
2. Same as before, you can customize paper size
3. You can't select paper tray (a workaround is print in Postcript, open the .ps file and print with the printer settings dialog customized to your likings)
4. You can print images in a grid, too (all cells same size, as before)
5. You can keep the settings for several prints
6. Again, can't test the borderless printing, but it allows you to set margin to 0... so maybe?

Have you tried Digikam?

I just searched for a simple way to print multiple photos on one page and found that LibreOffice Draw was the best application for my requirements.

You can select the resolution, the page size and even the individual image size, you can place the images manually or in a grid.

All the other programs I tried (including but not limited to: geeqie, gthumb, imagemagick, photoprint, gimp) didn't work for me.