I would elect Newfoundland as a possibility (where I grew up), given that the island lies on the same latitude as Seattle and Paris (covering 108 860 km², with elevations ranging from sea level to above 800 m) and yet is enveloped in fog, rain, sleet or snow for all but two months of the year.
Of all the major Canadian cities, the capital St. John's is the foggiest (124 days, next to Halifax's 122), snowiest (359 cm, next to Quebec City's 343), wettest (1514 mm, next to Halifax's 1491), windiest (24.3 km/h average speed, next to Regina's 20.7), and cloudiest (1497 hours of sunshine, next to Charlottetown's 1818 hours). It also has more days with freezing rain and wet weather than any other city in Canada.
No place on the island is more than 100 km from the open Atlantic Ocean and so is always subject to the year-round modifying influences of the encircling cold waters. Newfoundland also has the strongest winds of any province, Catalina on the East Coast is the windiest location, with an average annual wind speed of 28 km/h.
Hours of bright sunshine for the island: less than 1600/year.