Thanks to inkjet printers, 13x19 isn't as uncommon of a size anymore. I actually have a print I bought that is 13x19, and have seen other photographers selling prints that size too. But you're right, you would still have to order a custom mat (I just checked, cost about $10 at pictureframes.com) for that size. And you actually wouldn't have to get a custom frame, you could get 16x20 and just get a custom mat cut to fit. You would have a larger border on two sides of hte mat, but that isn't a bad thing. This of course all assumes you are going to print the full 13x19 (just cause it can doesn't mean you have to ;) ).
But consider this, 8x12 and 12x18 are standard sizes, each is full frame from a 35mm format camera. 12x18 happens to be one of my favorite sizes to print, not too big, but not too small. Regular desktop printers can't do either of these, whereas the 13x19 printer can.
I have my own opinions on inkjet printers for photographic printing (it's not my first choice), but putting that aside, if I was going to buy a printer with the intention of making prints to sell or hang on walls, I would go with the larger size printer. If I was just looking for a good printer to do the occassional photo print, I would probably go with the smaller size printer. The difference in price between the two is also a factor, if they both fit the budget then that's great, but it would still come down to which of my two uses above am I looking for.