With the XML-RPC we can add text to the Company field, or add ID to CompanyID field to link to a company record.
It looks like with REST, we MUST create a company record and add the id to the contact if we want to list a company (or use a custom field). Is this correct?
Yes, the older XMLRPC API exposes a lot of “legacy” fields that aren’t currently in use in all versions of our software and will be phased out eventually.
Companies previously were just a string value on a Contact record, but currently are a record in their own right with relationships to other records. This change happened a few years ago and solved a lot of problems about variations in company names when records were being added.