I got an Athlon 64 3000+ retail (connected to an ASUS K8N-E board) with
the stock HSF. It does a decent job of cooling, but it's kind of loud.
I was surprised by how much noise it makes, considering it's a largish
fan that only rotates at 3300RPM.

Any suggestions for a quiet replacement fan? Could I find one that will
fit on the stock heatsink and plug into the three-wire fan jack on the mobo?

The reason I ask about that, rather than just an entirely new HSF, is
that I've heard the stock heatsink's thermal pad tends to glue the CPU
to the heatsink, and I don't want to risk breaking off any pins trying
to pry it off.