erm:

Is there any reason to think that gradient descent would be less affected on the initial conditions than the SGD? (different seeds giving similar accuracies)


The loss curve of GD is usually less noisy and the loss should decrease in each step.
Using SGD on the other hand gives you more noise, but also the final accuracy is often better than in GD. One might claim that the noisy updates add some regularization, but I’m not sure what the current theory is.
If random seeds give such different results, your overall training is unstable, which is a bad sign.



 erm:

I would expect strong differences if I would be working with a huge dataset as CIFAR-10 for example, but not with a small dataset as the one described.


I would expect it the other way around. From my experience, the more data you have, the less likely it is to get trapped in a local minima.
E.g. if you are dealing with the XOR problem, you might easily stuck in a local minima and the seeds might decide if your model trains fine or not.
If you are training on ImageNet, I doubt that the seeds will make a huge difference. The training success would most likely be defined by the overall training, model architecture, augmentation etc.