Go with the Med. I think I had the same dilemma as you, with a 9.5 shoe (Montrail Hurricane GTX), and a beefier 10 snow boot (HiTek). I initially sized the Micros to the larger boot, went with the Large, and they were ill-fitting on the runners to the point where they were twisting a bit and not seating correctly.
Luckily, I switched to the Med, and have been happy since. Better that they're a bit stretched/snug on the bigger boot than swimming on the runner.