I’m using the official Android Kitkat by @chrmhoffmann , which is reported to have a faster GPS TTFF.
Sometimes, however I need to kill the navigation app (in my case OsmAnd) and start it again. Then usually satellites are found in an instant and a fix comes only about 15 secs later.
For visualization purposes of GPS satellites availability I use SatStat.