Here are my delicious location links:

http://del.icio.us/jmatt.peterson/location

There are a lot of APIs if you are going from address, city, zip. All sorts of variations - free, commercial, metadata, super accurate, international, US only, shipping, etc.

There are fewer and they are less reliable if you have a latitude / longitude and want address, major intersection, city, etc.

Initially I'd code for phones that provide basic location information like lat/long/precision. Personally I've written code for the iphone and android. I'd avoid any of the older phones that don't provide some sort of API. Your initial users presumably will be techies with newer phones. If you have some initial success you can add support for older phones that don't have a friendly API.