There is no any different IC of atmega16 for 2 MHz and 16 MHz. Atmega16 support different clock rate from1 MHz to 16 MHz. You need to configuration of CKOPT fuse for set 16 MHz. Refer the datasheet of Atmega16 for more information.
No need of any extra componet for GPS navigator. You can coonect the GPS through UART port of Atmega16 and extract information from GPS String and display on LCD.