Hoy avancé un poco más e hice la prueba con un Arduino Nano en lugar de UNO que uso para los desarrollos, en algunas oportunidades se iniciaba con un LED (equivalente a un relay en la prueba) encendido...y a veces dos, ambos aleatorios. Luego de meditar un poco el problema y leyendo lo que alguna vez postié
acá, llegué a la conclusión que el bootloader del Arduino Nano chino era un cachivache y se demoraba demasiado en entregar el control al programa real. Buscando un poco por la web, encontré que ese bootloader - aparte de ser mas lento y demorar mas en entregar el control - al programa - solía tener algunos problemas de cuelgues (pero a mí siempre me funcionó bien).
Con el Arduino UNO no tenía problemas por que trae un bootloader mas moderno y optimizado (parece que los UNO míos si son originales

) que se llama Optiboot, que es mucho mas pequeño - uno cuarto del tamaño del viejo - y que entrega el control casi inmediatamente, así que dije:
vamos a cambiar el bootloader 
Revolviendo la web encontré
esta excelente página de un flaco que explica con lujo de detalles como se instala el Optiboot en un Nano...usando otro Nano como programador, así que tuve que adaptarlo para usar el UNO como programador...y anduvo como piña

(bueee...anduvo como piña luego de que puse el capacitor de 10uF que dice el flaco, por que si nó se pudría la transferencia del bootloader).
Ahora se comunica a 115K con la PC (antes lo hacía a 57800) y entrega el control en una fracción de segundo, aunque voy a tener que revisar si ya funciona OK o alargar un poquito la constante RC de la línea OE\, por que este bootloader es mas nuevo que el del UNO y tiene algunas cosas que podrían ser importantes, pero no he revisado el código para ver la demora en entregar el control.

Ahí en la foto se vé el UNO con el cablerío de programador ISP y el Nano ya flasheado y por probar un ejemplo de fade que trae el IDE para ver que tal vá.
PD: Ya que estoy, mejor flasheo todos los Nano que tengo.
EDITO:
Revisando el código fuente del Optiboot parece que demora 1 segundo en entregar el control, aunque hay algunas opciones de configuración alternativas pero eso requiere recompilar todo...y la verdad es que no quiero montar todo un sistema de desarrollo para recompilar el Optiboot ==> habrá que extender un poco la constante RC y listo.