That very thorough preview that came out a couple months ago addressed the lock times with and w/o AGPS. If you don't have access to the Nokia server, it takes a long time (minutes vs seconds). AFAIK, nothing has been changed nor is likely to be on that front. There's a bug report about similar problems (i believe on N810) and it sounded like there was a problem with caching data. Anyway, there are a few threads on here discussing that particular aspect of navigation, and you can read through the bug tracker comments for more info.

It's the mapping/navigation software that's a moving target. Ovi sounds like it will be a big disappointment in N900 edition. I'm curious to hear peoples' experiences with the other options.