GPS receiveres are availlable for serial UART ports and shoot be able to be used with MSX serial interface. I programmed it on HP jornada windows CE2 back in 1999 or something in C, the GPS I used needed serial port on 9600 bps. Ofcourse u can use a cd-rom drive with map data.

I think reading out the GPS part is easy, showing your position on a map will also be easy (vector based map data). Calculating route algoritm could be ported from C but even though pc/linux nerds say C compiles to code as fast as assembly, we MSX hardcore assembler programmers know thats BS

I think this is the main problem: make the MSX to calculate routes using a HUGE database can be sooooo sloooow, even coding in pure assembly. Maybe compiling a pre-calculated database?

Calculating actual position should be easy. Antenna in the Navigator i actually have can work even at 1200 bps. That should give enough time to MSX to make easy calculations and even refresh the screen at 1/2 times per second.
Actual navigation systems use a lot of tricks to calculate possitions and give a "real time" impression...