The sample frequency can be adjusted in the code of post #42 by setting the values of the A/D pre-scale bits (ADPS0,1,2) in the A/D control/status register A (ADCSRA) register. The A/D clock is FCPU (16 MHz) divided by the pre-scale (128 in code above) divided by the clocks per A/D output (13). The pre-scale is a power of two so control of the A/D sample rate frequency is pretty coarse (9615.4 Hz, 19231 Hz, 38462 Hz, ...) .
ADCSRA |= (1 << ADPS2) | (1 << ADPS1) | (1 << ADPS0); // ADC clock 128 prescaler- 16mHz/128=125kHz->9615 sps
Atmel-42735-8-bit-AVR-Microcontroller-ATmega328-328P_Datasheet.pdf, see "28.9.2. ADC Control and Status Register A"
Interesting that you got better results with a shorter sample length, I hadn't explored that yet, but was wondering if 1k samples was excessive. In particular, when this is extended to do multiple peak detection, it will have to calculate the correlation at more lags, not just until it finds the first peak, and that's going to be slow with an excessively long sample buffer.
In the limited testing that I did, I was seeing frequency reports that were within 1% of what I expected. Most of the error looked like bias rather than random error, which would be consistent with the Arduino Uno clone's ceramic resonator being the dominant error source.