When GPS can't see satellites, how can I continue to tick off a smooth-ish time?
What you want, namely something to “smooth the received (GPS) time”,
is called a GPS disciplined oscillator. Obviously, you are not
after the high accuracy of commercial GPSDOs, but the working principle
of what you are describing is essentially the same.


  what do I do when the GPS can't find a signal?


In GPSDO lingo, this is called the “holdover” state. At this point you
rely solely on your local oscillator (here, millis() or micros()),
and steer it to correct for is natural drift, as determined while the
GPS reception was good. Or you can go fancy, measure the chip
temperature, and apply a temperature compensation.


  I'm somewhat aware of DIP methods, but I'm not sure how to apply them
  here


I guess you mean “PID”.

You apply this to the phase of the oscillator. If the local oscillator
is ahead of the GPS (positive phase error), you lower its frequency. For
example, you could increment the seconds count every 1,000,100
microseconds (as measured by micros()), instead of every 1,000,000.
This will make your clock a little bit slow, and resynchronize it with
the GPS. Conversely, if your clock is behind the GPS, you slightly
increase its frequency to make it run faster.

In other words, the error value of your PID is the phase error of your
clock, and the control variable is the frequency adjustment. By
applying the PID technique this way, you are building what is known as a
phase-locked loop, or PLL. This is the standard way of
implementing a GPSDO.


  It seems that someone must have solved the problem for the sake of
  syncing internet time


Sure, but NTP implementations can be quite complex, as they have to deal
with multiple servers having different round-trip delays and different
levels of trust. I am not aware of any Arduino library that does
anything similar. You may search for “time synchronization” or “PLL”. If
you don't find any, you can pick a PID library and apply it to your
oscillator.

A couple of final remarks:


You wrote “speed up and slow down by several percent over the course
of a few minutes isn't uncommon”. This shows there is something
awfully wrong with either your Arduino or your code. Over a few
minutes, you expect frequency variations of the order of one part
per million on an Arduino clocked off a ceramic resonator, and a few
parts per billion if yours is clocked off a crystal. See this
experimental study on the stability of an Arduino clock.
This stability problem is the very first thing you should investigate
and fix.
Many GPS modules have the option to give you a 1PPS (one pulse per
second) signal. If you can use this signal, you may get a quite
accurate measurement of your phase error. Relying on the NMEA
sentences will give you lots of jitter, which you would then have to
compensate for by setting the time constant of the PLL to a very long
value.