You must have a faulty phone. I can turn GPS on from within GPS Test and start getting satellite locks almost instantaneously, even indoors (Sprint). I have five Garmin units, including the high-end 3590LMT and the GS3's performance matches up extremely well.
I have a razr maxx and a now the S3 and my gps works very well. Was a little leary from going from a Motorola to a Samsung again but I'm very pleased with the go's in this device. Also if you dint know already turning on WiFi helps establish a faster GPS connection, even if it's not connected to a active WiFi. Downside it may use a little more battery.