which HTC Magic did you try out? I have the one with the larger RAM and I find the performance to be really good.
IMO, Android does a lot for the minimal hardware it runs on, which could be bad for the iPhone -- iPhone OS requires more expensive hardware and is not as featureful.