I live in the Highland neighbourhood of St. Paul. It's a little bit farther from your typical university housing (approx. 7 miles SE of the Minneapolis campus). However, there are buses that run to my area almost all the time (not so much on the weekends, but I typically either work remotely or drive to school). The reason is I, for one, do not want to live in the hustle and bustle of college (undergrad) life. But it's a matter of preference.
If you like the undergrad atmosphere, Dinkytown is your best bet. It is also closest to the campus. If you want to live a little bit farther but yet not too far away, try the Uptown area or the St. Anthony Park area (closer to St. Paul campus). You can try the CTC or the CSCC which are suited for grad student. Or rent an apartment in those areas. The Twin Cities is an awesome place to live with beautiful hidden gems that await you to find out.
I paid slightly more than $550 for a spacious studio apartment. Utilities and off street parking are included in the rent (no cap). The only thing that I pay extra every month is internet. Depending on where you rent and what kind of apartment (1 BR, 2 BR, etc) you are looking for, I think you could expect about $500-$600 for a decent studio or 1 BR apartment outside the 5 miles radius of the campus. The closer you get to the campus the more expensive it is. But you could expect to pay about $300 if you share.
Regarding the nasty winter... I am from a tropical country right on the equator and I thought I would never survive it. But here I am, loving this place more than ever. Invest on a good winter jacket (no, the fashion ones do not really work) and a pair of winter boots. You would be fine.