Il flash delle ROM di solito ripulisce il telefono, infatti... sono le applicazioni "di dubbia provenienza", e soprattutto l'install/uninstall che lo sporca
L'opzione di backup automatico è stata introdotta nel Samsung con Froyo, quindi è molto recente. Ad esempio sul HTC Desire l'avevo già vista in passato.
Credo effettui qualche backup o sulla memoria interna del telefono (/sdcard/Android/data) oppure sull'account di google associato al tel.
Anche se non ne ho visto traccia, sul mio...
Riguardo alle ROM, scegli e provane tu. Ce ne sono di molto molto valide nel forum, di almeno 2-3 esperti. Più o meno ottimizzate.
E si, prima e dopo ogni upgrade con Odin è richiesto un wipe completo, dati e cache. Di solito è indicato nelle procedure di installazione delle ROM.