I'm strongly in the Nautilus-could-use-a-makeover camp. It fulfils its intended roles quite well, but the user interface could certainly use a designer's touch. There's a lot of duplicate functionality and wasted space, and especially in the light of the popularity of netbooks, that's something you don't want.
Below is a screenshot of my Nautilus. The issue has been raised a number of times already, but a perusal through the various interface widgets in a default Nautilus window reveals numerous widgets that duplicate functionality. Because of the breadcrumb bar, the up button is duplicate. The stop button has become a relic. The reload button, while useful in some cases, takes up too much space compared to its importance. The home button is useless too; use the sidebar. And so on.
By carefully redesigning Nautilus' interface, you can save a tremendous amount of screen space. The funny thing is, though, that every Nautilus mockup I've seen more or less comes down to "make it like the Finder", and the most recent one, by Ian 'Izo' Cylkowski, is no exception. Note, though, that this isn't necessarily a bad thing.
The interesting part here is that Izo took it a step further, and also thought about Zeitgeist integration when designing his new Nautilus. Currently, you access Zeitgeist mostly through GNOME Journal, which presents the data collected by Zeitgeist in a usable way. Izo argues, correctly so in my opinion, that Zeitgeist should be integrated into Nautilus, eliminating the need for GNOME Journal. The mockup is entirely self-explanatory.
I'm hoping that a redesign of Nautilus is high upon the GNOME developers' agendas. I personally prefer Thunar, but since it's not possible to integrate Thunar into GNOMe without losing Nautilus' desktop, I just stick to Nautilus (at best you can have Thunar open using the Places menu; otherwise you must replace the Nautilus desktop with Xfce's).