I have the Android phone HTC Magic. Great phone that suits well my needs for GMail and Google Maps. However, the agenda is crap with Google so i still carry my old Palm for that.
I bought the phone with Android 1.6. Then Google has thrown the 2.1 update and it has become slow unfortunately. I may buy a faster HTC Android phone in a few months.
Google for z4root, install and run it, Reboot.
Install ROM Manager from the market and use it to install ClockworkMod Recovery, then use it to download and install a 2.2/2.3 ROM + Google Apps.
It will back up your old ROM so it's safe.