So everyone is talking about Cuil and how Google is not worried.
I tried a few searches and I think it's actually pretty neat concept. It's very categorical, which allows for easier exploratory searching than Google, and it uses the screen real estate evenly when returning results. It's too bad it doesn't have a quick Wikipedia link.
My critique is mostly from a usability perspective and goes to how they have images beside entries, which I consider distracting for anything but logos, and the somewhat arbitrary placement of things in the page. In a regular search engine, users expect items with the highest relevance near the top, so it's easy to develop spatial memory and just look at the first 2 or 3 links. In Cuil, there's no no-brainer way of figuring out which one is the highest relevance link without putting a bit of effort into actually scanning the page. Also, they could align the entries so that they are always the same width and height and so that they don't scroll off the page.
I've also come across many links within the UI that gave me no results. I get that in Google sometimes too, but far less often. Another thing that could be better is the page loading speed.