Wow. I certainly missed a major thread here. And I am drooling over those bags Vivian posted!
I think your main hurdle is going to be your climate of extremes. Summer shoes will be easier to source -- canvas options will help. Birkenstock copies for casual. Dressier sandals might be harder due to the sweaty feet issue, but at least with open tops you have a chance for some ventilation and also the fit may be easier to finesse. And in cooler weather the perspiration issue won't be as problematic, so a closed vegan shoe should be do-able once you find some styles you like.
But winter boots. Oy. I know they do make good socks for Bogs and Hunters, so that would get you through milder times. But in Winnipeg, if you are spending significant time outdoors, you need a genuine winter boot. The Kamik boots I used to have had no leather -- just a sort of nylon padded fabric with rubber or vinyl bottoms of some kind. They were rated to -40 and were super warm. You do need to size up in an insulated boot of this kind. Mine were not super stylish but they were cuter on than you might imagine.
I applaud you for attempting to follow your beliefs in this. It can be quite difficult, especially in Canada, for all the reasons we've mentioned -- fewer retail options, climate, etc. I really like Angie's suggestion of small steps and Echo's reminder that the perfect is the enemy of the good. Just deciding to take some small step and moving forward is an honourable decision.