Transparency around what the problem was, why it happened, and how it was fixed.

Receiving a non-defective replacement. The phone that caught fire in the article was a replacement.

Go through the CPSC to initiate a recall properly instead of trying to do a fly-by-night recall that confuses all of phone providers. Give people actual information about why, how, and when these batteries fail instead of just nebulously blaming the batteries that came from your own factory. Don't ship people replacement phones that still spontaneously ignite.

Around 2001 there were all kinds of laptop battery recalls, where they would send you two new ones and a box to return the old one; that's above and beyond. Since battery replacement is not applicable and advance shipping a $$$ phone return is a big risk, Samsung could have worked with carriers to authorize replacement of carrier branded models at the carrier store, even if original purchased somewhere else. If the phones are serviceable, they could have made a replace the battery while you wait program, so people don't need to transfer data etc.