I'm tackling a binary classification task, data is class-balanced. I'm training a multi-layer perceptron on this data. To estimate accuracy on unseen samples, I decided to perform $10$-fold cross validation. However, estimated validation accuracies on the $10$ folds have high variance ($\mu \simeq 63\%, \sigma \simeq 3\%$).
My first reaction was suspecting this is due to the random initialization of the neural network and local minima. So I decided to repeat the training/validation for each fold, to see if the variance was caused by local minima. I was wrong. The model does a consistent job within the same fold, it appears that some folds are "easier" than others.
What does this tell me about the dataset? What can be done further to have a better estimate?