How to create entity reference field from custom entity to another custom entity?
Yes, I was right, right after I posted the question I checked if I'm missing the entity_key label, and I was. I added it in the entity annotation definition, like so:

entity_keys = {
  "id" = "id",
  "uuid" = "uuid",
  "label" = "title",
},