If on the "second restart in normally starts up fine", then perhaps it is not actually shutting down but instead entering some sleep or hibernate or hybrid sleep, power saving state from which it is not able to recover and when I say "it", it could almost be anything..... most likely the GPU but potentially any hardware device / driver package that supports it.
So you might start by investigating if the machine is truly shutting down completely and follow that up by checking and confirming that you have all the latest drivers for all your hardware devices, including BIOS, Chipset, GPU, Audio card, etc., etc.,