Listen for USB "TX signal received" response on RX
If an MCU which has a built in USB interface (such as the ATmega32u4 on a Leondardo) is properly configured and connected to an operating USB host, it will receive a "Start of Frame" packet every millisecond.  I'm not very familiar with the details of the USB engine on that particular chip, but generally you can detect this as an interrupt, or as a change in a peripheral status register bit.

Going a step further, in the Arduino API an if (Serial) test will determine if the board is connected to a host which is in an active CDC-ACM "serial" session with it, ie, one that has a serial terminal or other program talking to it.  Again, this only applies to those that implement USB within the chip on which the sketch is running.

Chances are your problems can be fixed by enabling the AVR watchdog timer at one of its longer limits and resetting it in the USB ISR found in USBCore.cpp Then if the the USB goes down (ie, the usual every millisecond SoF interrupt fails to happen for several seconds) your Arduino will reset.  In the simple case, it will keep resetting as long as it has power and the USB is down, but you can put some startup logic to wait for the USB while resetting the watchdog if that bothers you.  See for comparative example the implementation details behind the if (serial) and create something similar for your chosen USB mode.