In the English language, three titles within Commonwealth Realms refer to the same office of head of government: “first minister,” “premier,” and “prime minister.” One of my correspondents informed me of a fourth title found within the Commonwealth of Nations: the heads of government in the several Indian states go by “Chief Minister,” while the head of government of the Republic of India goes by the conventional “Prime Minister.” The same goes for the heads of government of the United Kingdom, New Zealand, and Canada and Australia at the federal level. The heads of government of the Canadian provinces and Australian states are referred to as “premiers”, probably in order to distinguish them from each country’s federal prime minister. The heads of the governments of the devolved jurisdictions within the United Kingdom – Scotland, Wales, and Northern Ireland – became “First Minister,” probably to differentiate them from the Prime Minister of the United Kingdom. (I often use “First Minister” as a convenient generic label that would cover both provincial and federal heads of government in Canada and Australia).
In contrast, the French language only includes one title that covers all four of its English equivalents, premier ministre. Unfortunately, the most bizarre form of pedantic antipathy that English-speaking Canadians sometimes show toward Quebec is the critique that Quebeckers refer to their premier as “prime minister,” as if to elevate the province to the equivalent of a fully sovereign state. I’ve heard this nonsensical assertion on many occasions, and I’m sure that many you have as well. Worse still, some English-speaking scholars, like Sujit Choudhry, have even promoted this bizarre claim:
Quebec’s political elites have long referred to the province, its institutions, its symbols and its collective goals in national terms. The provincial legislature is the National Assembly, its head of government the Prime Minister as opposed to a mere Premier […].
In the French language, the title premier ministre applies to all 10 premiers in Canada, not just to the premier of Quebec, because of a fundamental fact of the French language that has nothing to do with nationalist or secessionist politics in Quebec. The “Premier of Ontario” is le premier ministre de l’Ontario – and no one would suggest that this French-language title would amount to an aggrandizement of the office.
Ironically, however, the use of “Prime Minister of Ontario” in English does propagate a political statement and seeks to elevate Ontario to the level of Canada. Leslie Frost served as the 16th Premier of Ontario from 4 May 1949 to 8 November 1961 – but he referred to himself as “Prime Minister of Ontario” rather than as “Premier of Ontario.” As the two photos in this blog entry show, several plaques on buildings that he commemorated have etched this title in stone. I found the first in downtown Toronto, and the other comes from the Tory Building at Carleton University. Frost’s moniker built on another precedent of self-aggrandizement: Ontario also dubbed its provincial legislature the “Provincial Parliament” and “Members of Provincial Parliament” in 1938. 
Frost reportedly enjoyed good relations with both Prime Ministers St. Laurent and Diefenbaker, so he probably did not adopt the title “Prime Minister of Ontario” in order to anger or challenge the federal level.  Canadian political scientist Rand Dyck concludes that Frost’s premiership “was characterized by […] a lack of concern with provincial status.”  (Perhaps Frost merely concerned himself with his own personal status!)
John Robarts also preferred the title “Prime Minister of Ontario,” as his address to the Law Society of Upper Canada in 1970 shows. But the last long-tenured premier of the post-war Progressive Conservative dynasty, Bill Davis, switched the title to “Premier of Ontario”, where it has remained since. Perhaps “Prime Minister of Ontario” sounds self-aggrandizing, but the first minister possesses the prerogative power to alter his own title.
*Update: 2016-06-28: I thank Pierre Allard for having taken an interest in this old entry and for having informed me that it was Davis who changed the title.
 Sujit Choudhry, “Bills of Rights as Instruments of Nation-Building in Multinational States: The Canadian Charter and Quebec Nationalism”, University of Toronto Legal Studies Series, Research Paper 1006905 (August 2007): 1.
 Rand Dyck, Ontario Government and Politics. (Ottawa: Carleton University Graphic Services, 2009): 36.
 Rand Dyck, Ontario Government and Politics. (Ottawa: Carleton University Graphic Services, 2009): 37.
 Rand Dyck, Provincial Politics in Canada: Toward the Turn of the Century. 3rd Ed. (Scarborough, ON: Prentice-Hall of Canada, 1996), 327.
The “provincial parliament”, on the other hand, seems to be a deliberate poke at CA 1867 s. 17, “There shall be One Parliament for Canada, consisting of the Queen, an Upper House styled the Senate, and the House of Commons” and s. 69, “There shall be a Legislature for Ontario consisting of the Lieutenant Governor and of One House, styled the Legislative Assembly of Ontario”. This was in the heyday of the provincialist Judicial Committee whose decisions contributed so much to an expanded sense of provincial autonomy and even perhaps of a status coequal with that of the dominion, so I suspect this change in language was part of the larger move away from the explicit provisions of the original Constitution Act.
I suspect there has been a fair amount of fluidity of usage in the past as opposed to the current fairly clear distinction in Canadian English usage. I remember well how the British PM was regularly referred to as “Premier Wilson” on the news when I was a child in the 1960s. I also came across an interesting usage of “Prime Minister” in this quote from Viscount Haldane in Stephen Wexler’s article “The Urge to Idealize: Viscount Haldane and the Constitution of Canada”, in the McGill Law Journal, Vol. 29, 1984: p. 638:
«Before long I had a very large business as a Junior in the constitutional cases from Canada in the Privy Council. Ontario gave me its general retainer, and I appeared for the Prime Minister, Sir Oliver Mowat, throughout his struggles with Sir John MacDonald [sic], the Prime Minister of Canada, for the right of the Province to pass its own legislation.»
It’s always a possibility that Haldane’s sense that the provinces should be given the same status as the dominion in relation to the imperial centre motivated him to use the same term for both the dominion and provincial first ministers, but I would want to find more evidence before allowing myself the liberty of making that conclusion.