The reason @alx mentioned is the main reason and applies in your case too.
When you are providing your images to the model, if there is particular similarity between many of instances for instance, just providing indoor images/stree/etc, your model will learn less features to understand the differences even though all classes exist in all images(although I many segmentation tasks, this does not apply). So, at the test time/validation, your model did not learn enough about different type of images.
A more mathematical explanation would be the issues regarding updating gradients. For instance, providing an image of street then jungle, enable model to capture more general features rather than overfitting on particular type of color/construction/texture/… .
In the end, I think shuffling data during training is mandatory unless we care about order of data.
bests