Your choice will depend largely on your motherboard's capabilities.
If your board can scale its HT ("FSB") above 300MHz (say, 320+), then the 165 is the best choice.
But if it struggles to reach 300, an Opteron with a higher multiplier works better.
Assuming all other things being equal (which, in practice, they're not), all dual-core Opterons will roughly have the same maximum potential (circa 3.0GHz).
Stepping information is only really useful as a rough guide, a kind of estimate of mathematical probability as far as overclocking potential. But, to answer your question, the steppings with the best reputation are definitely the CCBBE 061Xxxxxs (meaning, a dual-core with "BB" memory controller version made sometime in the 10-17th month of 2006).
You do not need to reformat/reinstall Windows when popping in a new CPU (at least, I've never had to do so, and I've swapped lots of chips in testing).
Hope this helps! And good luck.