You have the same issue that 35mm film photographers always had. Standard photo paper sizes are 5x7, 8x10, 11x14, 16x20 -- none of which match exactly. 4x6 is the same ratio. 5x7 is close, and as you noted, 8x12 is right on. My local lab makes 10x15 inch prints, and I make 12x18 and 16x24 inch prints on my Epson printer at home.
6x6 film photographers have whole different set of issues <grin>.
You have two choices:
1. Shoot and print "full frame" and don't worry about the paper size. So you would print 6x9 inches on 8x10 paper, or just get 8x12's, etc. There would be lots of extra white space around your image area.
2. Realize that the aspect ratio of your camera isn't always the best ratio for the image, and crop away. You may end up with something that fits standard paper, or not. The final image could be square, panoramic, 4:5, whatever.
--Ken