How to poll UART while processing lots of other stuff
I believe some of the dsPIC family have DMA support in the MSSP peripheral, that will allow buffering of the input stream without cpu intervention up to a point, limited by available memory.

Use an interrupt for processing the GPS data in chunks, just make sure the interrupt for your video processing work is set to a higher priority so it can bump the GPS handling interrupt.