I've been in Winnipeg since 1994. If I was moving here, all over again, I'd live in Alberta.
Other than that. The cheapest and homes with the safest, most family like neighborhoods are Transcona. That said, its very far from the base. Depending what you drive, you'll spend $400 a month on gas getting to the base. Therefore, why not buy a home in Headingley, Charleswood or St James instead. Shorter commute, money in your home instead of the Sheik's pocket for oil and gas.
Manitoba has a high tax rate (provincial) expect to see a decrease in your take home. Property taxes are still a bit high, but have been frozen for years, they are not 'unfrozen' so should be going up this season. Yay.