February through August, multiple times, 1969.
(TL;DR)
Q:
What was the first unplanned "over-the-air" software update of a spacecraft?
A:
Mariner 6 and 7 probes, launched in 1969 to observe Mars, differed to the earlier probes in having new computers that could be reprogrammed.
This allowed, for the first time, changes to be made to the missions that were unplanned prior to launch.
- So, reprogramming, whether planned or unplanned prior to launch, would have been impossible prior to the CCS computers launching on the Mariner probes. So the earliest date for a OTA software update to any spacecraft, at all, would be these two probes in 1969.
(This also led to the reprogrammable and backup computers being used on the Viking missions, which in turn used identical hardware on the 1977 Voyager missions with software improvements allowing the mutiny of Voyager 2 to be subdued.)

Mariner 6 and Mariner 7 were identical spacecraft launched on February 24, 1969 and March 27, 1969 respectively, and their missions were entirely devoted to the flyby study of Mars.
In transit to Mars, likely due to a battery rupture, contact was temporarily lost with Mariner 7 on July 30. After a 7-hour silence, contact was restored, but it soon became evident that the instrument responsible for reporting the orientation of the television cameras had been damaged and was no longer functioning. Without this information the Mariner 7 cameras could not be pointed properly and, with the Mars encounter close at hand, a solution was needed quickly.
On August 1, manual calibration by ground crews brought Mars into the view of Mariner 7 cameras and, on August 2, Mariner 7 began to relay far encounter images of Mars. The restoration of the Mariner 7 imaging system was a prime example of the expertise being developed by mission operators during these early interplanetary missions and the event stood as a testament to the importance of having a reprogammable computer on the spacecraft.
https://nssdc.gsfc.nasa.gov/planetary/mars/mariner.html
The new Central Computer and Sequencer (CCS) system, used for the first
time on this mission, which allows extremely flexible spacecraft operation using in-flight reprogramming of the computer memory by radio command .
Previous ...missions employed a relatively simple fixed-sequence device having a series of events preprogrammed and hard-wired prior to launch.
The only events that could be changed after launch were the turn durations, midcourse velocity increment, and the time of midcourse.
The difference with this new system was ..although this flight program is loaded into its l28-word memory prior to launch, the CCS may be completely reprogrammed in flight by radio command.
During the flight of the Mariner VI and Mariner VII spacecraft, the CCS has been reprogrammed many times by ground command. As of June 17, 1969, the Mariner VI had received 575 radio commands and the Mariner VII had received 217.
The flexibility allowed by the reprogrammable CCS permitted the operations team to carry out many sequences that had not been previously planned. It has also enabled alternative approaches when problems in other spacecraft subsystems have occurred.
As an example, calibration and testing on the Mariner 1969 spare television system indicated that the automatic aperture control had been positioned in a
manner that could cause excessive brightness of some of the early near encounter television pictures. This was a result of abrupt brightness changes sensed as the television field of view swept across the line separating the darkness of space and the bright limb of the planet. The CCS was reprogrammed by ground command to cause an automatic sequence that would hold the camera aperture control at a minimum- gain position through several pictures, after which it would go into an automatic compensating mode.
This is only one example of many instances where the CCS has been reprogrammed to adjust for performance variations so that the spacecraft is able to carry out a nominal mission in the event of failure of the command system occurring at a later time.
Discussion at the end of the paper:
Q. You mention that the magnitude of flexibility increased the efficiency. What do you mean by efficiency in this connection? Was it calculated or measured?
A. The improvement in the efficiency of the Mariner 1969 mission is one example: during the time after closest approach to the planet, approximately 300 commands were sent to the spacecraft to reprogram the digital computer on board, which allowed the spacecraft to perform a series of manoeuvres which completely map the sky in the ultra violet.
This was a mission which had not been designed into the spacecraft prior to launch, but was made possible by our being able to reprogram the control system from the ground.
Mission improvements were made by reprogramming the digital computer.
https://www.sciencedirect.com/science/article/pii/S1474667017687755
In-flight reprogramming, begun when the programmable sequencers flew on Mariners, and brought to a state of high quality on Mariner X, was a nearly routine task by the time of Voyager's launch in 1977. Both the CCS and Flight Data System computer have been reprogrammed extensively.
https://history.nasa.gov/computers/Ch6-2.html
On an end note, not the first but certainly one that came to my mind immediately, aside from Viking and Voyager (through looking at Viking I noticed Mariner..), for reprogramming was the International Sun-Earth Explorer-3 (ISEE-3) satellite - reprogrammed to become ICE.
https://en.wikipedia.org/wiki/International_Cometary_Explorer
and finally, a video:
Mariner 6 and 7 Programs Missions to Mars, 1969 HACL Film 00033
At 8:58 it mentions the commands being sent to Mariner.
and lastly, this reminds me of Voyager, but in reverse:
https://meh.com/forum/topics/building-the-plane-on-the-way-up
When the Voyager probes were launched with Reed-Solomon encoders on board, no Reed-Solomon decoders existed on Earth.
Also, as an aside:
The Voyagers original control and analysis software was written in Fortran 5.
NASA Study on Flight Software Complexity
Growth in Code Size:
1969 Mariner-6 (30)
1975 Viking (5K)
1977 Voyager (3K)
1989 Galileo (8K)
1990 Cassini (120K)
1997 Pathfinder (175K)
1999 DS1 (349K)
2003 SIRTF/Spitzer (554K)
2004 MER (555K)
2005 MRO (545K)
1968 Apollo (8.5K)
1980 Shuttle(470K)
1989 ISS (1.5M)
https://www.nasa.gov/pdf/418878main_FSWC_Final_Report.pdf