Meanwhile, I have a phone with nearly identical specs to the iPhone 3GS (a Motorola Milestone), and it "feels" slower than my first-gen iPod touch, which manages to do beautifully smooth scrolling with really wimpy hardware.

I don't know the technical details (though I'd assume hardware acceleration is a big deal), but evidently Apple can achieve a good user experience while consuming far less resources. It's taken Android years, and I probably have to buy a new device.