To protect your privacy, it is commonly recommended to send change to a new freshly generated address. It is argued that this makes it impossible to distinguish the payment from the change which makes it harder to group the transactions that belong to you.

Correct me if I'm wrong, I'm afraid it doesn't help in many cases. The reason is simple: payment value is usually smaller than the change.

When I spend money from my debit card, the payment amount is usually much smaller than the remaining balance. That's because I don't want to refill my card as often as I spend. The same spending habits applied to Bitcoin make transactions traceable.

If you have 10 BTC (say, you received it from an exchange) and want to pay 1 BTC, your transaction will have two outputs:
1 BTC - the payment,
9 BTC - the change to another your address.
Without any other knowledge, just by looking at the output values, it is usually safe to say that 1 BTC is the payment and 9 BTC is the change, and the address where the 9 BTC landed is again your address. Any other coins received to this address will be tracked to you. The subsequent transaction that spends the 9 BTC will be tracked to you.

Any thoughts how this situation is really often and how to protect one's privacy?

I like the dice example, there is one small difference though.
If the controversial block was block number 1001 then the miners who initially rejected it (segment B) will continue working on another version of block 1001 while the miners who accepted it will switch to block 1002. That means, for segment B to win, it'll have to produce 2 blocks (1001 and 1002) faster than equally powerful segment A produces one block 1002. This probability is low, and segment B is probably wasting its resources.

There is no long term damage anyway.

No obvious benefit to the miner, just a short lived disruption of the network (I don't think it is big enough to qualify for a DoS). If successful, it would split miner resources and cause the next block to be mined at half speed.

The main point here is that relying on node current time is dangerous for consensus. Even if it doesn't cause major trouble, it complicates things. Fortunately the 2h rule is the only place in bitcoin protocol that instructs node to make a decision based on its own clock.

Great. That means the chances of quick recovery are high.

Every block includes a timestamp as set by the miner who mined the block. There is a rule that other nodes reject the block if its timestamp is more than 2 hours in the future. It is a hard limit: if the timestamp is 2:00:01 in the future relative to node time, the node rejects it; if it's only 1:59:59 in the future, the node accepts it.

What happens if a miner finds a block and sets its timestamp exactly 2 hours in the future relative to some accurate time source? Since the clocks of all other nodes are never perfectly synchronized and distributed somewhere around the true time, I would expect that approximately half of the nodes (whose clock is slightly ahead of the true time) accept the block, while the other half will reject and forget it. Half of the miners will accept the block and start building a new block on top of it (with half of the original hash power), the other half will continue working on the previous block. We've got a blockchain fork caused by misbehavior of just one node. One of the two forks will eventually win but, before that, transaction confirmations might be delayed. Did I get anything wrong?

I think when designing a distributed consensus system, such as Bitcoin, one should be cautious about making a decision based on node time. Node time is different at different nodes and this a source of disagreement that potentially destroys consensus. Hopefully just temporarily.