How to factory reset without data loss and undue pain?
AppBrain will make it easy to restore your apps. After the reset, install AppBrain first(ish) and use it to get back all the apps you had before. (Sync before you reset.)

Market will remember your paid apps so you'll be able to get those without having to repay.

Your Google app data (e-mail, contacts, calendar) are backed up to the "cloud" already, so you shouldn't have to do anything special with them. If you REALLY want to you could export them to a CSV file, but you shouldn't have to.

You probably don't need to, but I would copy the contents of the SD card to a temporary location. Just in case.

As for other apps that keep data only local...I can't speak to those. I know that for myself everything important has a backup somewhere else. (Yay Dropbox!)

Unfortunately (or, actually, fortunately), I don't have any personal experience with a factory reset. Everything I've read says that it's really not that bad, excepting those apps that don't have dynamic storage strategies.

Good luck!