Do you control power to the GPS?

The sequence of what to do depends on who powers up first. You probably shouldn't assume that the mcu is powered up and initialized before the GPS. It would be good to know how long the GPS takes to powerup and start sending those initial strings.

The sequence might look something like:

- wait several seconds at powerup for the GPS to initialize
leave the uart set for 9600 baud
You'll likely miss any initial serial transmissions that the GPS sends you, but that's ok.

- send a string to the GPS that you know the response for, and wait for that response with a timeout.
The simpler the better... a single response that's easy to parse would work a lot better than a sequence of responses.
loop doing this until you have sync with the GPS.

- now you can switch to 38400