ManGo
ManGo is a chain store locator with a very good native Google Maps implementation. You can select the category, then the type of place and it displays all the results on the Maps. You can save locations to favorites and also browse the for the newest restaurants/stores in your town. The look and feel of the map is same as that on the native iPhone Maps.
Map: Google Maps (native)
Price: Free
