Google just gave us a new one. And boy is it good. First, it gives us what Google does best: a simple search. You can simply type the whole search in the single simple input field and get your results. Second, it gives a very slick interface that allows us to interact with the map without getting a full page refresh (I assume it's based on the same concepts as their Gmail interface). The last feature, and this is under-appreciated one, is that the maps they give us are big and clear. A search for a particular address will give you a zoom level where streets have width (rather than lines). The maps are the easiest to read of any of the map services I've used.
Another cool map service is Map 24. It does give us a lot of Google does, and has an even slicker interface. It does this by loading an applet, instead of Google's javascript magic. This also makes it a bit slower to get started, however. I think Google's going to get most of my usage, though I plan to keep Map 24 in mind for times when I want to explore around an address more.
Yahoo! Maps, Mapquest, and Microsoft MapPoint: they aren't even in the same ballpark.