OpenStreetMap to the rescue! Its cycling map shows contour lines and shaded relief (even in Canada):
(source: opencyclemap.org)
Like most open data projects (probably Natural Earth, too), they use NASA's SRTM (OSM Wiki) dataset that has global coverage, as far as I know. As you seem to need contour shapefiles, refer to the article Contours (OSM Wiki) for a workflow on how to convert raw SRTM data to shapefiles using GDAL.
Jackpot: Apparently, OpenDEM went through the effort of preparing contour shapefiles worldwide from SRTM with 25m precision. They offer a pretty convenient download for an arbitrary region. (Download manager or wget recommended.)
How I found the data: For all my spatial data needs, usually before googling, I have a look at the OpenStreetMap Wiki and search for relevant keywords, in this case: contour, height, SRTM.
