I would go with Garmin Mobile XT. It's $99 but it's a one time fee. I am using it on my Verizon HTC Touch Pro 2 and it works great. No extra charges from Verizon and they didn't block the GPS. If you can't find what you are looking for in the pre loaded point of interests you can do a Google search and it will bring up just about anything just like it was a pre loaded point of interest, as well as find the cheapest gas near you, traffic updates, etc.
You can check it out here:
https://buy.garmin.com/shop/shop.do?...413#featureTab