I've found the Motorola Droid, with Android 2.0, to be quite smooth and responsive. It's not quite up to the iPhone's well-oiled level of smoothness, but I've never seen the "jerky menus" people talk about either -- just the occasional one-frame pause when scrolling a graphics-heavy web page.
I looked very heavily at the Droid before I got my iPhone, and it felt far less polished than the Apple offering. Plus, Verizon's decision to not include multitouch staggers me -- pinch to zoom is one of the things that makes web browsing on the iPhone usable, IMO.
The Droid also has no IME, and rotating the device when in the web browser seemed to have no effect whatsoever, and a CDMA-only phone is, to me, as a communications device, marginally less useful than a brick.
That said, I don't think it's a bad phone, and Motorola seems to be selling a hell of a lot of them. The hardware feels to be very good quality, and when Google works out the Android UI quirks, it'll be one hell of a platform, especially because there's no App Store Nazi sitting between the developer and the customer.
So, the Droid is not in the same area code as the iPhone, but unlike a lot of other phones on the market, it's at least on the same planet, in terms of usability.
The hardware and SDK have multitouch; there's a browser called Dolphin which has iPhone-style zoom gestures. I suspect they did not implement it in the default apps because Google wanted the Android install to be a reference implementation.
However, I found myself going back to the Google browser: on a double-tap, it switches between a website overview and a zoomed view which intelligently sizes itself to the width of the text column you're reading. I've found it much easier than manually zooming to find a comfortable reading magnification.
In my experience, when held between a 45 degree angle and exactly upright, the screen re-orients itself on rotation faster than an iPhone. When overtilted (so the screen points downward), it does not respond -- which is nice when you're lying in bed holding the phone up above your face.
I got my Droid on launch day, so it's definitely one of the same phones that have given people negative impressions. Maybe there are differences in manufacturing quality? I'm open to the possibility.
> pinch to zoom is one of the things that makes web browsing on the iPhone usable, IMO.
I have a Windows Mobile phone with Opera and, as the other commenter also said about Andriod, it has the double-tap to zoom and reflow the page. There is a dedicated zoom area on my phone (I just have a swirl around the center hardware button like an older iPod) but I never have the need to use it. I find I really only the two levels of zoom -- the full page zoomed out and the reformatted in-zoom.