Share your experience!
Have you tried to set location on high accuracy?
Try another app like the free version of Copilot - I'm not a fan of Google maps and have had issues with it in the past but never with Copilot but I use the paid for version
Sounds to me like you are getting confused with your GPS and your Compass...
GPS provides position but not heading, this function is provided with the Magnetometer / Compass...
Goto you dialer and enter *#*#7378423#*#*
Select Service Tests
Select Compass and follow the onscreen instructions.
This will calibrate your compass and give you a more accurate heading in your apps...