Took a quick look at the Digikey and of the chips they've got the largest FIFO buffer available is 256bytes. I think you need at least 1k to really benefit from an external UART - and I think the interface would have to be parallel or really fast SPI or you'll spend most of the time sending data to the UART just as you would when using the on chip UART.

What would be ideal is a PIC with DMA but that feature doesn't exist in the 16F or 18F series. But really, this should be totally doable with a PIC and on chip UART but it'll take some careful planning.

/Henrik.