OP: I went through this when I moved from Tiger to Leopard. You need to back up:
iTunes library (i.e. the iTunes folder in Music)
Address book database
iCal database
Mail database (if you're not using IMAP)
This document tells you how to back up address book, iCal and Mail in Tiger: in Leopard it's
file > export > address book archive, file > import > address book archive to restore
file > back up iCal, file > restore iCal to restore
Mail is the same as Tiger AFAIK
When you've reinstalled the OS, just restore all of the above (copy the itunes folder into your new Music folder and overwrite the existing empty one, restore the rest as in the article) then sync as normal.
Alternatively I think you could just reinstall, sync the phone then merge the data from the phone with the data on the mac to restore the address book and iCal. Not done this myself, I didn't really trust it (too many bad experiences with Windows Mobile I think).