Find out what the local lab processess (as much as Velvia would be wonderful, it is E-6 and not easily processed here - mail away only). If you are prepared to shake it up at home Ilford HP5+ is very versatile, and Delta 100 is super fine grained. Both can be processed at home with some simple instruction - well documented on Youtube. You can often find used Patterson tank set ups for cheap in the classifieds or at the local shop.
If you are looking at C-41 there is plenty of choice out there. You're heading into rainy winter weather, so you'll be looking for ISO 400 probably. It costs me about $10 per 36 roll to acquire decent quality colour film, and another $10 to process it - I scan my own negs. The lower quality can be had in three packs for ~ $18. All prices in CAD.
Some images posted here. I always try to tag camera, lens, and film type.
Shooting film gives one great perspective on the value of full frame, the severity of "noise" at high iso (my K5 IIs eats 400 ISO film for breakfast as far as image quality goes.) Have some fun with it but dont get over invested (Like I am).