te recomiendo que utilices un pic con dos usart...

sobre el tema de las velocidades....
no es necesario que los puertos trabajen demasiado rápido...
con 9600bps, puedes leer las tramas nmea sin dificultad.
y para la aplicación que creo que estás trabajando, el modem, no necesita tampoco comunicarse a una velocidad demasiado rápida....
yo trabajo en una plicación similar, y hasta el momento a 9600, ha funcionado bien...