I made a new account here just to post this. I just got my first iMac a few days ago but have been using iPhones for years. Never had Android. I was having the problem where only SOME of my contacts' names missing on my iMac, but others were fine. I rebooted, upgraded my iCloud storage, updated my OS, did all the things. I trouble-****.
Here's what finally worked for me:
It turns out for the past few years, all the new Contacts I've added to my phone have been being synced to my gmail account and not to iCloud. In my iPhone, I went to Settings --> Contacts, and the Default Account was NOT iCloud. (HINT: It's supposed to be iCloud)
Then, also in my iPhone, I went to Contacts --> Groups (in the upper left)
and was like, WTF I didn't even know that was there, when did that even happen?
I deselected iCloud and found all the Contacts that were missing from my iMac. So annoying.
Anyway so then on my iMac I went to Internet Accounts and added in that one Google account. Then in Contacts I went and copied and pasted all those people from the Google group into the iCloud group. Removed the Google account from Internet Accounts and now I can go to sleep.
Hope this helps someone.