Was it? My memory is that there were GPS watches (e.g. Garmin) before GPS became common in phones. Wasn't the miniaturization already there by the time phones started integrating GPS?

It's all about power -- the computation required for processing the signal in the presence of noise, multi path fading etc. The RF part is not the limitation.