What replacement SMS/MMS app for iPhone will allow me to change convo color, etc?
There are loads of "messaging" apps on the App Store, however, none of them use SMS. And if they do, it's one-way, it's send only. All the rest of them are data calls using an external service that invariably requires registrations, and (in some cases) perhaps payment!

This is one of the infamous "duplicates Apple functionality" zones. There is one way in or out of SMS, and that's Messages.app built into the iPhone. It is unfortunate that messages can't be customized beyond how it works external to the app, and the minor details such as showing a subject field, counting characters, etc.

Without Jailbreaking, you will not find a full on frontend replacement for communicating via actual SMSes in the iOS App Store. Other, more "creative" solutions must be done here.

Per @mankoff's comment on your question itself, you could perhaps find a better way to have his name displayed, be it by Nickname or other ways.