Something to point out here that I think a few of you are missing...
GPS, in and of itself, does not require a phone service. It uses the satellites in orbit to determine your location. All you need is a clear, unobstructed view of the sky for it to work properly.
The GPS the Droid uses is a combination of using Cell towers as well as GPS satellites. The Cell tower approximation is a rough guestimate, but 10m accuracy comes from the standard GPS.
Google Maps requires a Data Connection because of the design of the application. It downloads the map information directly and works with the GPS radio to determine your current position on map.
Other GPS based apps, depending on how they are designed, will either make use of or not use of the Data Connection. Generic GPS apps, like telling you coordinate information or compass information will NOT require a data connection, as it is purely reading from the basic GPS, like a hand-held GPS device does.