Microsoft is releasing improvements to it's MSN Search engine. If Microsoft is going to compete with Google I think they have a long way to go. Still I believe that competition in this field is healthy as we still have a long way to go with web searches.
Some things I'd like to see:
Tracking the things I'm looking for as a user to help improve the results of searches I do.
Use of color (or graphics) to categorize results
Location aware searches, the search engine would take into account your location when doing the search, so if I search for "I want to see the Spiderman movie, where is it on?" it shows me where it is playing locally.
Better English language translation on the search request as in the previous example.