Tyll,
For your walks download a free app call Runkeeper, it's pretty cool.
And you don't even have to hit navigate if you're really lazy. On the home screen just press and hold the search button and the voice recognition system should open up. Speak, "Navigate" followed by the address and it should take care of the rest. Also, here's to hoping the Incredible gets some of the more recent updates to the Android OS (it's one version behind right now, or my wife's is) which should offer some nice improvements to the UI and performance. One more thing, I agree, the iPhone OS is not superior in my experience to Android. It has some better points, but Android has just as many to counter if now more at this stage.