My first-gen Moto Droid did fine with Google Nav. You're downloading waypoints and relatively simple maps, and uploading waypoints or positions. 3G should be perfectly fine, it's not like you're downloading tons of hi-res images.
You can cache maps, but if you go off route it may need a connection in order to find you a route.