they wouldn't be able to broadcast the block without the actual raw transaction. (or would they? Please CMIIAW)
They would be able to share only the block header. Because to share the actual block, all nodes need to know all transactions behind that. So, it is a game of incentives: there are hashes here and there, and it is a matter of planning, what to share, where, and by whom. Because the reward for the puzzle is something, which can be compared with the basic block reward. So, if one side can say: "we can sweep your reward, if you give us your public key", then another side has similar tools to say "we will keep our spending transaction secret, so you won't be able to do that, and you will lose a block". So, the risk is then on both sides: a key owner risks losing the reward from the puzzle, but the mining pool also risks losing a block.
And in mining, every millisecond counts so if the transmission of raw transaction isn't coordinated well and quick, other pools/solo miners could broadcast a block in their place.
This would need a specialized software in both miner's and user's side to be automated for low latency.
Exactly. It is hard to do, but it is possible to make it trustless.
Good idea, but I'd like to know how can this be applied exactly to existing P2PKH outputs like what OP is pertaining to?
For example, it is possible to spend some coins from such script, and get that transaction deeply confirmed. Then, every mining pool can see, that "the first person, who announced 'I have the public key' signal, is in transaction X, so that reward should go to address Y". And then, it is possible to prepare for claiming that reward, by creating an agreement with major mining pools, that they will accept only a transaction, sending coins to address Y. Then, if some pool will sweep those funds, it will be possible to show everyone a publicly available proof, that "funds from this puzzle were stolen by pool Z". And I bet if no pool will take a risk of destroying their reputation like that, then claiming the reward will be successful.