We know that at the completion of the Execute Cycle, a test is made to determine whether any enabled interrupt has occurred or not. If an enabled interrupt has occurred then Interrupt Cycle occurs. So can the computer respond to the interrupt after the first instruction is executed after the computer is turned on?
Yes it is possible; if unlikely and perhaps not on all architectures.
On ARM Cortex-M for example, the start of the vector table includes the execution start address and the initial stack-pointer - these are loaded to the program-counter (PC) and stack-pointer (SP) registers on start-up and execution starts at PC. At this point the NVIC will not be initialised and interrupts will not be enabled, however it remains possible for a non-maskable interrupt (NMI) or an processor exception to occur that will invoke whatever handler is specified in the vector table.
For an exception handle to be invoked, your "first instruction" would itself have to be invalid. And if you have an NMI occurring that early; your system is possibly broken or poorly designed. The occurrence of an NMI in any case is normally to indicate some critical error external to the processor.