I'm newish to canada too (1.5yrs).

When I landed I went to TD Canada and got the first class visa infinite thing. If you sign up for a select service you get the card for free, and no bank fees if you keep 5k CAD in your account. But as you need that 5k for security anyway it works out.

I've found them to be a decent bank. But on the whole banks in canada are terrible.

HSBC typically have good deals if you're newly landed too.