>I have yet to find a suitable replacement for Google Maps - OpenStreetMap is still really hard to use and gives bad directions.

I block all Google products (at the router level), and do miss their Maps/Earth products.

The best non-Google mapping I've found http://www.bing.com/maps (no affiliation, just ¢¢)

It has so much integrated information, without being annoying (e.g. store listings); also is the only free product I know with built-in tilt-shift perspectives (from each major of eight cardinal directions).

In my neck of the woods OpenStreetMap is way more accurate than Google Maps. Map is less noisy visually, and if there are any errors in the map, I can fix them myself and see results immediately.