Right after device reset may have a different time than if a GPS app has been run since the last reset. How long it's been and how far you've moved since a GPS app was last run also may make a difference. The GPS may appear quick if you haven't moved since last using it, since it might first report the last cached location before getting a new fix. How close you are to a cell tower or known wifi access point may also make a difference. How many satellites are overhead and not obscured by trees or buildings. And Etc.
Restarted iphone 3g, took iphone outside and pressed locate button, it took about 4 seconds for the blue dot to appear, and it appeared in the correct place. I think it has improved alot.