Montreal seems like the place to be if you're starting small. Vancouver might have a stronger talent base but their startup culture is a little top-heavy -- it's mostly VCs and angels spinning off their own ideas, whereas in Montreal there's a vibrant startup community and VCs are actively seeking early-stage concepts to invest in (like here: http://montrealstartup.com/). And yeah, it's a beautiful city and housing is really cheap. I'd move there if I could but the only startups looking to hire talent are the well-funded ones in Vancouver.