My wife flew out of Calgary several times this year and they did not ask her to remove her shoes. However she did have to remove her laptop from the new open flat bag that the TSA lets you leave your laptop in here.
We flew out of CDG in Paris in February and shoes were not removed.