Concerning to the Arduino platform, it seems still do not provide relevant support for real interrupt handling, I mean, I would expect that at each received byte from UART the ISR vector would be instantiated, instead of having to check if there is any data at the received buffer.
I can't see how could use a GPS at baud 9600 and with a frame of maximum 75 bytes per second, it's a real chalenge. Do you think that it is possible to achieve with the standard Serial library ?