How much can we change our bike wheel diameters before needing another bike fit?
The thing about bike fit is that it's almost exclusively about relating your body position to the mechanical parts of the bike. The relationship between handlebar, saddle and pedals is unaffected by changing the wheels.

If you make a change to one wheel diameter it will be equivalent to the tiniest of slopes. Let's take a worst case: Say you go from 35mm tyres to 25mm on the same rim (a 10mm difference in nominal radius, which is what actually matters) on a bike with an unusually short 1m wheelbase. That's a 1% change. Does your fit change on a 1% slope? More typical changes on more typical bikes  would work out closer to 0.2%. I doubt you can even measure whether the saddle is level to that precision, for example, never mind whether it should be. You'd have to change the bead seat diameter for it to make much difference, and while people do put 650B wheels on 700C frames they normally do both at once. 

Shoes are very different, in that they come between your body and the bike, and in a particularly important way.