Handling dimensions for RGB data with Keras CNN
Strangely, if change the label's fake data to size=(500, 10) then it &quot;works&quot;. But obviously that makes no sense, since it would mean I have 10 labels for each sample.

It would most certainly not mean that; it simple means that, for the type of softmax classification you are attempting here with CategoricalCrossentropy loss, your labels should be one-hot encoded, and not single digits, as here (hence the error).
You should

Either convert your single-digit labels to one-hot encoded ones using to_categorical (docs)
Or change your loss to sparse categorical cross-entropy (docs)

Changes in your code for the first approach:
labels_ohe = tf.keras.utils.to_categorical(labels, num_classes=10)
# [...]
model.fit(data, labels_ohe)

Changes in your code for the second approach:
model.compile(optimizer=keras.optimizers.RMSprop(learning_rate=1e-3),
              loss=keras.losses.SparseCategoricalCrossentropy())


The MNIST dataset that works which I refer to can also be found in the linked documentation.

The MNIST labels, like the CIFAR10 ones, are also single-difit integers and not one-hot encoded; your MNIST model from the example you refer to you works because of the loss=&quot;sparse_categorical_crossentropy&quot; setting.