In reply to Mr. Lee:
> ... I use Gaia often and my location sawtooths all over the place when recording, unless I have Strava running simultaneously...
That suggests that there's nothing wrong with your phone, just that Gaia has a problem (e.g., doesn't use the Android Location API correctly). If so, then changing phones is unlikely to be a good solution.