user16606: I've a wall clock (sorry, code's a mess, look for updateClockVars) which makes use of the Timezone library (and ultimately Time). Nothing fancy, call millis() every loop; turn to Hrs, Mins, Secs; display on LEDs.
The magnitude of the drift I am seeing on my 2 Arduino Pro Mini - compatible boards - up to ~8% lag, not a typo - blows my mind. Replacing the 16MHz quartz with one bought at a local retailer didn't help much (~33% improvement). Is something else at play here?

user16458: TL;DR You're doing it wrong. Use RTC.
Ok, longer explaination is required here. millis() is not accurate and here is why.
First, grab official Arduino source code from their Github repo.
The file Arduino-master/hardware/arduino/avr/cores/arduino/Arduino.h
contains few interesting macros (I'm pasting grep output here):
Arduino.h:#define clockCyclesPerMicrosecond() ( F_CPU / 1000000L )
Arduino.h:#define clockCyclesToMicroseconds(a) ( (a) / clockCyclesPerMicrosecond() )
Arduino.h:#define microsecondsToClockCycles(a) ( (a) * clockCyclesPerMicrosecond() )

At 16MHz clockCyclesPerMicrosecond() will evaluate to 16. Keep this number in memory.
Those macros are used in Arduino-master/hardware/arduino/avr/cores/arduino/wiring.c:
// the prescaler is set so that timer0 ticks every 64 clock cycles, and the
// the overflow handler is called every 256 ticks.
#define MICROSECONDS_PER_TIMER0_OVERFLOW (clockCyclesToMicroseconds(64 * 256))

// the whole number of milliseconds per timer0 overflow
#define MILLIS_INC (MICROSECONDS_PER_TIMER0_OVERFLOW / 1000)

MICROSECONDS_PER_TIMER0_OVERFLOW macro is evaluated as (64 * 256)/16 -  a dodgy looking 1024. Look how they round it down to calcuate MILLIS_INC.
Let's assume that you run your Arduino with ideal main clock signal.
At 16MHz main clock, the timer frequency is 1.024kHz, not 1kHz. This results in 2.4% inaccuracy. You can get away with that in most cases, but not when you're building a clock.
This 2.4% error is best case. Your main oscillator is not 16MHz - it has it's own inaccuracy, that is unknown and it sums up.
You should use an external, accurate time reference provided by RTC module. When assembled properly, they guarante low time drift, temperature compensation and other goodies. Be smart - use RTC. :)
If you are scared of I2C RTC modules, you may find my tutorial
and another tutorial on MCP7940N RTC module. Know-how is applicable with other RTCs as well.

user7508: Expanding on my previous comment...
As I said before, I suspect the NeoPixel library to be blocking
interrupts for too long when you strip.show(). If a timer interrupt
fires while interrupts are blocked... it's not a big deal: the interrupt
request is put on hold and serviced as soon as interrupts are enabled
again. If two timer interrupts fire while interrupts are blocked...
you have a problem: the interrupt service routine will be called only
once, and your clock will miss a tick.
Craig has worked out the timings in his answer: the timer interrupt
fires every 1.024 ms, and NeoPixel blocks interrupts for
1.8 ms. So it is perfectly expected that, from time to time, you
will have two timer interrupts within this 1.8 ms window.
Here is a quick hack that could solve your problem: if you
strip.show() right after a timer interrupt is serviced, then only
one more interrupt should fire during the subsequent 1.8 ms window,
and you should be fine. So you could simply add this right before
strip.show():
/* Wait for a timer interrupt to be serviced. */
uint32_t lastMillis = millis();
while (millis() == lastMillis) /* wait */;

A possibly better solution would be to avoid blocking interrupts for so
long. NeoPixel blocks them in order to comply with the very tight timing
requirements of the WS2812 LEDs. But it turns out the WS2812s are not
nearly as picky about timings as their datasheet suggests. You can drive
them in a more relaxed way, with interrupts enabled except for 1-bit
durations, and they still work fine. For a detailed explanation and
sample code, see NeoPixels Revealed: How to (not need to) generate
precisely timed
signals.
A third solution would be to follow the general advice given here and
grab an RTC. However, although it certainly is a good and clean
solution, I have to admit I completely agree with your comment “I still
didn't catch WHY that is better – it's a quartz either way”.

user337: The problem is the interaction between the interrupt handler that updates the value for the millis() function and the neopixels show() function.
To maintain the counter for the millis() function a interrupt is triggered approximately every 1.024 ms.
When the show() function is called all interrupts are disabled to get the precise timing needed to send the data to the neopixels.  For a 60 led strip this takes about 1800 microseconds (60 leds * 24 bits * 1.25 us per bit) so at least one interrupt is skipped each time you update the display.
This page has details about how the millis() function works.

16606: <p>I've a <a href="https://github.com/mamert/iot-a/blob/master/_60_led_clock/_60_led_clock.ino" rel="noreferrer">wall clock</a> (sorry, code's a mess, look for <code>updateClockVars</code>) which makes use of the <a href="https://github.com/JChristensen/Timezone" rel="noreferrer">Timezone library</a> (and ultimately <a href="http://playground.arduino.cc/Code/Time" rel="noreferrer">Time</a>). Nothing fancy, call millis() every loop; turn to Hrs, Mins, Secs; display on LEDs.</p>

<p>The magnitude of the drift I am seeing on my 2 Arduino Pro Mini - compatible boards - up to ~8% lag, not a typo - blows my mind. Replacing the 16MHz quartz with one bought at a local retailer didn't help much (~33% improvement). Is something else at play here?</p>
 16458: <p>TL;DR You're doing it wrong. Use RTC.</p>

<p>Ok, longer explaination is required here. <code>millis()</code> is not accurate and here is why.</p>

<p>First, grab official Arduino source code from their <a href="https://github.com/arduino/Arduino" rel="nofollow">Github repo</a>.
The file <code>Arduino-master/hardware/arduino/avr/cores/arduino/Arduino.h</code>
contains few interesting macros (I'm pasting <code>grep</code> output here):</p>

<pre><code>Arduino.h:#define clockCyclesPerMicrosecond() ( F_CPU / 1000000L )
Arduino.h:#define clockCyclesToMicroseconds(a) ( (a) / clockCyclesPerMicrosecond() )
Arduino.h:#define microsecondsToClockCycles(a) ( (a) * clockCyclesPerMicrosecond() )
</code></pre>

<p>At 16MHz <code>clockCyclesPerMicrosecond()</code> will evaluate to <code>16</code>. Keep this number in memory.</p>

<p>Those macros are used in <code>Arduino-master/hardware/arduino/avr/cores/arduino/wiring.c</code>:</p>

<pre><code>// the prescaler is set so that timer0 ticks every 64 clock cycles, and the
// the overflow handler is called every 256 ticks.
#define MICROSECONDS_PER_TIMER0_OVERFLOW (clockCyclesToMicroseconds(64 * 256))

// the whole number of milliseconds per timer0 overflow
#define MILLIS_INC (MICROSECONDS_PER_TIMER0_OVERFLOW / 1000)
</code></pre>

<p><code>MICROSECONDS_PER_TIMER0_OVERFLOW</code> macro is evaluated as <code>(64 * 256)/16</code> -  a dodgy looking <strong>1024</strong>. Look how they round it down to calcuate <code>MILLIS_INC</code>.</p>

<p>Let's assume that you run your Arduino with <strong>ideal</strong> main clock signal.
At 16MHz main clock, the timer frequency is 1.024kHz, not 1kHz. This results in 2.4% inaccuracy. You can get away with that in most cases, but <strong>not when you're building a clock</strong>.</p>

<p>This 2.4% error is best case. Your main oscillator is not 16MHz - it has it's own inaccuracy, that is unknown and it sums up.</p>

<p>You should use an external, accurate time reference provided by RTC module. When assembled properly, they guarante low time drift, temperature compensation and other goodies. Be smart - use RTC. :)</p>

<p>If you are scared of I2C RTC modules, you may find my <a href="https://iobtoolkit.com/docs/tutorials/i2c_terminal_mcp7940n.html#mcp7940n-chip" rel="nofollow">tutorial</a>
and <a href="https://iobtoolkit.com/docs/tutorials/i2c_python_mcp7940n.html" rel="nofollow">another tutorial</a> on MCP7940N RTC module. Know-how is applicable with other RTCs as well.</p>
 7508: <p>Expanding on my previous comment...</p>

<p>As I said before, I suspect the NeoPixel library to be blocking
interrupts for too long when you <code>strip.show()</code>. If a timer interrupt
fires while interrupts are blocked... it's not a big deal: the interrupt
request is put on hold and serviced as soon as interrupts are enabled
again. If <strong>two</strong> timer interrupts fire while interrupts are blocked...
you have a problem: the interrupt service routine will be called only
once, and your clock will miss a tick.</p>

<p>Craig has worked out the timings in his answer: the timer interrupt
fires every 1.024&nbsp;ms, and NeoPixel blocks interrupts for
1.8&nbsp;ms. So it is perfectly expected that, from time to time, you
will have two timer interrupts within this 1.8&nbsp;ms window.</p>

<p>Here is a quick hack that could solve your problem: if you
<code>strip.show()</code> <em>right after</em> a timer interrupt is serviced, then only
one more interrupt should fire during the subsequent 1.8&nbsp;ms window,
and you should be fine. So you could simply add this <em>right before</em>
<code>strip.show()</code>:</p>

<pre class="lang-cpp prettyprint-override"><code>/* Wait for a timer interrupt to be serviced. */
uint32_t lastMillis = millis();
while (millis() == lastMillis) /* wait */;
</code></pre>

<p>A possibly better solution would be to avoid blocking interrupts for so
long. NeoPixel blocks them in order to comply with the very tight timing
requirements of the WS2812 LEDs. But it turns out the WS2812s are not
nearly as picky about timings as their datasheet suggests. You can drive
them in a more relaxed way, with interrupts enabled except for 1-bit
durations, and they still work fine. For a detailed explanation and
sample code, see <a href="http://wp.josh.com/2014/05/13/ws2812-neopixels-are-not-so-finicky-once-you-get-to-know-them/" rel="nofollow">NeoPixels Revealed: How to (not need to) generate
precisely timed
signals</a>.</p>

<p>A third solution would be to follow the general advice given here and
grab an RTC. However, although it certainly is a good and clean
solution, I have to admit I completely agree with your comment “<em>I still
didn't catch WHY that is better – it's a quartz either way</em>”.</p>
 337: <p>The problem is the interaction between the interrupt handler that updates the value for the millis() function and the neopixels show() function.</p>

<p>To maintain the counter for the millis() function a interrupt is triggered approximately every 1.024 ms.</p>

<p>When the show() function is called all interrupts are disabled to get the precise timing needed to send the data to the neopixels.  For a 60 led strip this takes about 1800 microseconds (60 leds * 24 bits * 1.25 us per bit) so at least one interrupt is skipped each time you update the display.</p>

<p><a href="https://ucexperiment.wordpress.com/2012/03/16/examination-of-the-arduino-millis-function/">This page</a> has details about how the millis() function works.</p>
