I have not done my Sparkle PS yet, but I have done an older, cheaper PS. Taking out the old fan and putting in a new one is easy. It takes 10 minutes, maybe longer if it is your first time.
There are several 80mm fans that you could use. A few of the quietest are:
Papst 8412NGL - 19 CFM, 12 dBA - $18.10 + S&H
Enermax Thermal Fan - 22 CFM, 18 dBA - $10 + $4
Papst 8412NGML - 26 CFM, 19 dBA - $18.10 + S&H
Panaflow P80L1A - 24 CFM, 21 dBA - $9 + S&H
ADDA - 26.2 CFM, 22.5 dBA - $8 + $4 S&H
Take a look at
GiZzO's Fan Page for more information on fans.