I find Yandex (in English) interesting.
I've used it a few times recently. The results page is nice and restful. It's just got, uh, results ;)
Incidentally, their Webmaster Tools has a nice feature. They list all your indexed pages by name, so you don't have to figure out what they missed. The whole list shows up right away, even if you've just that moment signed up. (If you combined the best features of all the search engines' webmaster tools, you would probably come out with a single handsome application. My favorite Bing feature is the error-type breakdown.) Excluding, of course, the four pages in Unsupported Languages.