You could, in fact, offer a third size: a standard 16x20 frame with a print matted to approx. 12x16.
With regards to "whar's normal", there are differing views as to how tied people are to, as you correctly say, budget and, in addition, how tied people are to their pre-conceptions.
If you are producing for the budget conscious, the stick to normal frame and mat sizes. That may mean compromising your cropping/composition, but that's the price you pay for standardization. Remember, though, you have two standards you can work within... The old 11x14 & 16x20 and the new as Jeff mentioned, 12x18 and 8x12. (Then, there's the IKEA standard which is different again, but with the frames so cheap, you could offer the whole package at a reasonable price.)
If you want to take the extra step of cutting your own mats, then you can be a little more forgiving with the aspect ratio within one of the standard mat sizes. Sell the print in the mat with backing (actually a standard practice not only to protect the photograph, but to present it as you want it presented). Your customer can then buy there own frame and all is well.
The unfortunate part in all of this is that you become more of a mat (and possibly frame) buyer and cutter and assembler, etc. with less time actually doing photography. It's a trade-off for sure. Good luck with it!