I have an HTC hero with Android 2.1, and the latest Skype available in android marketplace (december 2010) stutters badly on wifi.
(I did not even try to make a skype call over 3g data, i think that would be silly, and in my market where data charges are exorbitant, a waste of money.)
I believe it's a performance problem with my phone. I have tried to uninstall some other apps, and not very much seems to be open and running on my phone (just skype, the phone main UI panel).
Audio coming to my headphones stutters terribly and is full of clicks. The audio going out is reported to be bad when I tested it with human callers, but when I used the echo123 skype service, my audio came back to me mostly perfectly.
It looks like Skype's website lists the following as compatible android handsets: "Android devices: DROID by Motorola, DROID ERIS by HTC, Motorola DEVOUR™, HTC Droid Incredible, LG Ally, Samsung Fascinate™, Motorola Droid X, Motorola Droid 2, Samsung CONTINUUM, Motorola Ciena, Motorola Droid 2 Global."
[Note that HTC hero is not in that list]