Just released a new app called safe2pee. It's still in beta but it provides you a list of available bathrooms in your area. There is a normal street search and a proximity (address based) search. As of right now you have to type the address in manually but i'm working on using GPS to generate the list automatically & integrate it with Google Maps.
It's free and available on the G1 market!