Even though Deadly references adding 'weapon dice', is specifically exempt from changing its die size.
An ability that changes the size of the weapon's normal damage dice doesn't change the size of its deadly die.
Fatal is less clear, but I believe it would be affected by the Leshy ability, and other things that affect die size.
The fatal trait includes a die size. On a critical hit, the weapon’s damage die increases to that die size instead of the normal die size, and the weapon adds one additional damage die of the listed size.
It is changing the die used by the weapon, and does not preempt changing it like Deadly does. Arguably, this counts as an increase to die size and it could not be increased further, but the rules do not prevent you from both increasing and decreasing die size.
Where this gets really muddy is that Pathfinder 2e does not define the order of simultaneous effects. Are you allowed to decrease your die size then increase it to the Fatal amount? Or do both effects have to be carried out to the best of their ability? As a GM, I would have you used the Fatal die minus one step.