I used to be able to change my contact/conversation color in Android Messages. With that latest update I can't find this feature. Where should I be looking?
You can't change it. There is an ongoing discussion in Google product forums. You can give a feedback there as also from the app
uninstall this and find the previous version apk and install that / change the SMS app