My Sense location reading for widgets and such has been consistently accurate to within five miles, but only once (for five minutes, no more) on my actual location. I have very good reception all around the area, as far as both cellular and satellite are concerned.
Maps takes between ten seconds and ten minutes to find my location accurately (read: accurately), with around five minutes being the most common. Even while driving in clear, open areas with historically near-perfect reception of every type on my original Moto Droid, it takes quite a bit of time to get a lock. The "bubble of uncertainty" doesn't even come close to overlapping my actual location until it does get an accurate fix.
I do have the 2750mAH extended battery and case. Can anyone else confirm/deny these problems with the battery?