How do I update/change a company in a contact?

Hi @JPoppick , thank you for your post.

Do you mean you’d want to edit the associated company from a contact record? If yes, you can achieve this by clicking on “Remove association” as seen in the screenshot below:

This knowledge base article explains the details too: Associate records