They're not traditional UTXOs
Well, they are very similar. For each OP_CHECKSIG call anywhere, you have a signature, and a quantum-safe data around it, which are committed into r-value of the signature. It is not that much different, than having Segwit commitment in the coinbase transaction, but here, instead of taking additional on-chain bytes, things are simply committed to existing fields, and you replace one 256-bit r-value with another number, and everything else stays the same, from the perspective of today's node.
so there may be additional challenges in the case of reorgs
Proof of Work can solve them. As long as the majority of computing power is in honest hands, it should work. And if that isn't the case, then we are doomed anyway.
but Ethereum has these problems too and seems to work fine
They have a weaker security model, because they rely only on signatures, which means, that no Proof of Work is used to protect their cryptographical primitives, if they will ever be broken.
But isn't the complete verification cost (number of operations in a full node per signature) higher in this case?
It is, but it should be negligible, if you compare it with the cost of executing single OP_CHECKSIG opcode. And also, that kind of flexibility may be needed anyway, if the community wants to have covenants or vaults, or even batch verification, and packing multiple signatures into one. Which means, that if future soft-forks are going to introduce that kind of changes anyway, then quantum versions can simply have a different format, and avoid the need to explicitly introduce new opcodes for new features later, just because to get them, different parts can be moved from output scripts to input scripts, and it could be enough to have "sign any message from the stack" as a working feature, without OP_CAT or other new opcodes, which could open more unwanted use cases.
the sidechain security will always be at least a bit inferior to the mainchain security
It currently is, because there is no Merged Mining. But if it would be possible to mine sidechain and mainchain with the same power, then it would work better.
Also, Proof of Work can be used in many places, not only to validate sidechains. It is also possible to form Lightning Network channels with new opcodes and features (for example related to quantum signatures), and use Proof of Work in output scripts, to protect on-chain interactions from being double-spent. Then, if attacking the network would require some resources, it would be much harder to close some channel with some old state (because it would have less Proof of Work and less fees, so it could be easily detected, and ignored by mainchain nodes, without going into all details behind second layers).
