How important is shoe weight?
You are correct that the weight of the shoes cancel out each other for the rotation part. For an extreme example of the same effect, check out Falkirk Wheel, which lifts 250 tons of water and boat using same amount of water as counterweight. 

The shoes are not usually centered on pedals, but the axle is under the ball of foot. If hypothetical heavy shoe has even weight distribution, you will have to support the weight of the heel. That weight does not do any work, and it would be possible to design a gear train similar to Falkirk Wheel that maintained the pedals level without outside forces.