High side Driver Issues
You're only looking at Vg on the top fet, not Vgs, which is what actually turns it on.  Unless you know something which is not on that scope plot, then that first rising edge is not the top FET turning on, it's the source and gate rising up as the bottom FET turns off.  

This is what a typical high-side MOSFET driver does in a half-bridge - it floats the drive of the top FET on top of the upper/lower source/drain junction node.

Update:

OK, assuming that what I already wrote is not the confusion, here's a mechanism which can cause brief shoot-through on half-bridges with big FETs, though it happens at the top turn-on point, not the bottom turn off:

A MOSFET has an implicit capacitor between gate and source, which everyone knows about and is what you have to charge up to turn on the device.  However, it also has capacitance between drain and gate.  When the upper FET turns on, and pulls up its source, current flows through this capacitance in the lower FET into the lower FET's gate circuit.  Depending on how hard the lower gate driver and lower gate resistance hold the gate down, you might see it turn on briefly/slightly as its drain, and hence gate, is pulled up by the top FET.

This tends to be a much worse problem when the PSU is very lightly loaded.

The problem with just changing both gate resistors is that you don't see much difference, because although slowing-down the turn-on of the top FET helps, increasing the gate resistance on the bottom FET makes the problem worse, and the two effects cancel-out.

To start with, you could just slow-down the top fet by increasing its gate resistor.  You may then have to increase your anti-shoot-through delay to avoid problems in at the other end of the cycle, but I'd suggest you make that absurdly big at the moment anyway to eliminate that from your search.

I have ended-up with diodes around gate resistors in this situation, to allow me to set turn-on and turn-off rates separately.

You might find looking closely at both ends of your bottom gate resistor with the scope lets you see this happening.  It doesn't sound like you have a current probe available, but for the sake of experiment you could perhaps try adding some low resistance in the 0V line somewhere which would let you see exactly when the shoot-through current spike occurs.

You should post the schematic.