I would use some of the time during the house hunting trip to look at cars and identify a short list of makes/models that you like. Then start looking for available options a week or two before your move. Buying in advance and without an address is going to be too big of a hassle, as is storing it. Car dealers are typically open in the evenings and on Saturdays so just plan to rent a car and do the actual shopping after you’ve moved. Maybe you can delay your start date at work for a few days so you have some time to get stuff sorted out.
$15,000 CDN will be pretty limiting to your search. Not sure about Winnipeg but the used market down south has eased but is still tight. FWD with good snows should be fine up there, but you’ll need to budget those in. I just looked at Craigslist for Winnipeg and there are some very scammy listings (even for CL), so beware. $15k should get you a 10 year old Corolla or RAV4. $3k for a 5 YO car? Scam.