Yahoo! Site Explorer
The differences seem to be:
Google Sitemaps has a much better site map listing procedure and verification methods.
Yahoo! Site Explorer has better tools taht show which pages are indexed and what sites link back to you.
There are ups and downs to both, but if you really want to manage a site's optimization you need the big two. MSN where art thou? Anyone?