The host system already has a pretty robust brown-out watchdog circuit that generates the system reset signal. The reset gets held on power-up until about 1/2 second after the 5V power stabilizes nicely, which ought to give the oscillator way more than enough time to stabilize. So I doubt there would be any issues with setting the fuses to get the ATmega328 going right away after reset.
So I just tried setting the fuses for 1K + 14 +0mS, and now the startup time between reset and outputs doing their thing has dropped to less than 150uS. Working great now!
A big thank you to everyone who answered! 