IceRocket.com is a new search engine, that has some pretty cool features. The search results can contain a thumbnail preview of the home page of the resulting web site. Also it has a feature where you can email a query to them, and get an email response with the result.
I don't think that this will be serious competition for Google, but they do have some good features.