My understanding is that "nice URLs" and "RESTfulness" are orthogonal. Difference implementations of the same RESTful interface could have completely different URL formats and they should all be compatible with clients written to the interface specification.
Having said that, best to have nice URLs and RESTfulness.
It's in some ways quite anti-RESTful for a consuming client to start to try parsing a URL semantically. "URL building" is not something a client should be responsible for, it should be (semi-)blindly using URLs the service has provided for it.
maps.google.com/whatever-nice-text-describing-location?ll=lat,long
If the lat/long is missing, then ask Maps to do a search. If its present, then its just a "nice" URL. Not necessarily RESTful.
Edit: Formatting
Not by any meaningful definition of REST.