I do not own a Nexus, so I can't tell for sure. I never have troubles on my smartphone (so far
) nor on my GPS handheld (also: so far)
What I do know ('in general terms) is that GPS satellites move around the world and when you start up your GPS (on Garmin or on the NEXUS) it starts looking for the satellites at the position in the sky they (the satellites) were the last time the GPS was used, seen from the GPS point of view. It's possible the garmin was more successful for whatever reason while the Nexus GPS needed more time. Any "first" satellite fix can take a while, the same when you are "out of position" because your GPS supposes you are elsewhere (e.g. near home) and looks at the wrong position.
A-GPS can be a help for quicker fix as can GPSfix or GPS Status & Toolbox (that are apps). The latter one can download (by wifi or cellular) the latest positions of the satellites. A-GPS works based on cellular mode, I think.
Is this any helpful?