A9 is a search engine with a twist: you log into it using your Amazon.com account. It is then able to keep your search history and your bookmarks on their servers. Which means that you can log in from anywhere, on any computer with Internet access, and get to your bookmarks. It's beautiful! It has some cool drag-and-drop features (drag a link from your search results into your bookmarks). The best part is that it uses Google for results, so you don't have to give up the quality that you're used to. You just get these value-added features. It also has buttons to include movies (IMDB), images (Google Images) and books (searching inside via Amazon.com) (and a few other things) in your results.
The downside? No Google Calculator, no maps, no phonebook, no package tracking, no Google Local, no define: (though I usually use Merriam-Webster), no Froogle, no Groups, no News. And now, no Google Desktop.
Google Desktop builds a fast, searchable index of the hard drive on your computer. I installed it today and I already know that it will be indispensable. It searches into Office documents. It builds an index of your Outlook email. The slowness of Outlooks searches has been something that I've grumbled about for quite some time. Today, just to prove a point, I did an advanced search in Outlook for the word "twice" in the subject and message body of all of my email (about 90 MB). It took 45 seconds. In the era of Google, I'm sorry, but that's just absurd! With my newly-created Google Desktop index of my email, I searched for the same word. It took 0.8 seconds. I rest my case. (As an aside, the admin of the Exchange server turned on full-text indexing for my account on the server...I'll post here with results of that comparison.)
Google Desktop's results are tightly integrated with Google. When you search for something, if there are results on your computer, they show up in the top, just the way news results or Froogle results show up. Google Desktop is incredibly useful. It fills a pretty big hole in my computing life. It does what Indexing Service failed to do. It does what WinFS is promising to do. I think Google Desktop will be an indispensable tool for me until WinFS rolls around.
As for A9, I really like the server-side search history and bookmarks. I don't have to email myself links anymore. I just put them in A9. But knowing what you give up with Google, you have to know when to use it. For my average web search, A9 is king. For things I'm less certain about (especially programming-related, where answers are likely on Usenet), Google is the way to go. I guess that makes me a flip-flopper.
In summary: try A9, try Google Desktop. I like them both a lot, and I bet you will, too.