One of the delights of my spiffy Palm Centro is full support for Google Maps.  Including being "location aware".  This uses that technology which isn't GPS where cell phone tower proximity is inferred from signal strength, and your location is triangulated accordingly.  It doesn't locate you within three feet - more like 30 meters - but that's close enough for you to find where you really are, based on streets and so on, and from there it is really useful.  (It will say "your location within X meters", where X is a big number, but then puts the little blue dot very close to where you really are.)

The most excellent thing is searching for "stuff which is near you", and while at CalProg '08 I made use of this feature to great effect, finding a Starbucks within walking distance (crucial, addressing a serious caffeine deficiency), and later an Outback within easy driving distance (equally crucial, addressing a serious beef deficiency).  Once you've found something, getting directions to it from where you are is easy, and the step-by-step turn-by-turn interface is really nice.  You'll appreciate just hitting one [big] button when you've reached each intersection to move to the next leg if, say, you're walking or riding a bike.

I know, I know, it isn't an iPhone.  It's better.  Hit 0 and poof, blue dot.  Hit menu-S and poof, you have a search dialog.  And now you have a real keyboard on which to type "Starbucks" or "Outback" :)