Well, it depends on what part of Manitoba you'll be traveling around, and how long you're staying, also what types of images you like to make. Basically, though, you'll need to bring just about every piece of clothing you own... AND a parka. It's really hard to explain -40 to -50 deg C to someone who's never experienced it. Exposed skin freezes in a few minutes, and you'll need to keep your batteries warm. Actually, there are a few threads on these forums on camera use in cold weather so you might want to do a search.
Kenora is a nice place in its own way - in the summer time it's full of cottagers from Winnipeg, but in the wintertime you're not going to find so many. It's on the edge of the Laurentian Shield, so you're looking at rocks and trees and lots of lakes. Kenora is more 'true north' in that you're going to find some mining, some logging, real people living real lives. It's been a long time since I lived in that area, so it's probably grown up since then. I believe they've closed the mill, which your nose will be thankful for.
Most of southern Manitoba is pretty flat, open country, but Riding Mountain is on top of the escparpment. It's also nice country, a pretty good contrast to much of the surrounding country because of the forests. There's a bison herd there, that you're not going to find in Kenora.
BTW, Kenora is less than 2 hours east of Winnipeg, and Riding Mountain is about 3 1/2 hours west and a bit north. In case you want to run to Starbucks for a hot chocolate...
Mike.
P.S. They have bigger moose in Manitoba than they do in Ontario. You can tell from the pictures on the road signs! Trust me, I'm a biologist.