Softserial - max speed - loosing characters
This is a classic example of where you choose the wrong chip just because it's the most popular chip around here.

What you want is a dedicated hardware UART just for the GPS that isn't used for your debugging connection.

But, you say, you can't use a Mega because it's too big. And that's true as far as it goes. However, you have blinkered yourself into considering either a Nissan Micra or an 18-wheel juggernaut. You forgot the Ford Focus or the Renault Meganne.

There are other chips besides the (what is too under-specced for you) ATMega328 and the (what is too over-specced for you) ATMega2560. Chips that have other facilities.

Chips like the ATMega32U4 for example.

One hardware UART like the 328, which you can use for the GPS. One USB interface, which you can use for debugging.

And there are boards already with that chip on it - boards like the Arduino Leonardo, or the Arduino Micro.