Assuming you're pointing the device in the direction of travel, you can move forwards and combine the new position information to reduce this noise - I believe Google Maps does this on Android.
One could possibly envisage also using data from the phone's camera and corresponding it to street view images which (presumably) all have a known direction. There would be issues with the amount of data being sent up to Google to do this and the experience would be a bit wacky as you'd have to point your phone up (or at least horizontally, assuming you weren't surrounded by pedestrians etc) and maybe scan it around a bit...
You've got me thinking about Google Maps in general though. A feature I'd love to see is a map layer for mobile network coverage. I'm taking a trip this weekend somewhere quite rural and would like to try out the turn-by-turn directions, and it would be good to know ahead of time if some cruicial point in the route simply isn't covered by a signal - you never know until it's too late! They could perhaps combine this with the routing algorithm to offer you an alternate route where you don't have to make a turn in a no-reception area. When caching is implemented further down the line this could be used to provide a sensible 'minimal caching' option that just stores the bits you won't be able to receive on the road.