Arduino pitch detection in realtime (using autocorrelation and peak detection)

If I understand correctly, you're getting better results with a sample rate such that you get 3 or 4 full cycles of the fundamental frequency in your 500 sample buffer rather than just 2 full cycles.

One theory for why this might happen is that your audio source contains some non-harmonic content which is better rejected by the longer correlation interval, that is, the more cycles used, the more non-harmonic signal content decorrelates at the lag where harmonic content has peak correlation, thus distorts the correlation peak less. What are you using for audio in your testing?

Looking at your attached code, it looks like the sample rate chosen for B2 is around 60 kHz which seems unnecessarily high in any case.