I've never done this before? Are you even able to skip the iCloud login phase and start using the laptop? I thought that was mandatory to use a Mac (Mac n00b!3 here)Just wanted to let you know that I had the same issue with a new MacBook Pro, and 3 hours with Apple support did nothing to fix it. They actually claimed this probably was normal behaviour at the end.
Below solved it for me.
option+command+r, install,and no iCloud login or Touch ID set in configuration stage.
0 delay after above procedure.