Harper won a plurality of Toronto seats in 2011.
Precisely. Vancouver was governed by the center right for most the 20th Century, and usually votes that way in Provincial elections as well. John Tory, Gordon Campbell, Rob Ford, or abroad Boris Johnson or Jaques Chirac all conservative mayors at one point.
What appears to me to have happened is that the overwhelming cultural tribalism of the American right is simply repellent to naturally pragmatic urban conservatives, and as such the ability of Republicans to win big-city elections has withered.