My knowledge of French politics is fairly weak, so what follows will almost certainly need significant adjustment after input from the more knowledgeable among you. Have at it!
* * *
The POD (admittedly a rather easy and cliche one) comes in the Battle of Spicheren in August 1870. A German soldier stumbles slightly, throwing his aim off, and young French soldier Hubert Moreau is hit in the shoulder instead of the heart. For Moreau, who can only guess how close he came to dying, the rest of the war will be spent in a prison camp in Silesia (later to gain infamy as Stalag VIII-B during WWII).
When the war ends and Moreau is released, he returns home to Paris and, denied the military career he hoped for, joins his father's law business. In part to find a more hospitable climate for his perpetually painful shoulder, Moreau relocates to Algers, opening a branch of his father's firm there in 1875. Eventually, Moreau enters politics and, after a defeats in 1885 and 1889, is elected as one of the deputies from Algers in 1893. Moreau is relected in 1896 and again in 1902.
It is around this time that Moreau becomes the main exponent of Algerianism in the National Assembly. This philosophy, to simplify things greatly, aims to create a fusion of native and settler culture in order to create a new Franco-Algerian nationality. Moreau comes into his own, finally having a Great Cause to advocate with all the silver-tongued skill he gained as a young lawyer.
In the hallowed halls of the Palais Bourbon in Paris, Moreau gains a reputation as an exceptionally eloquent, quick-witted delegate. He argues for an expansion of the franchise in Algeria, shrewdly recognizing (far earlier than most even of his fellow Algerian delegates) that in the long run, Algeria cannot remain French unless the Algerians are made French, or at least Évolués (Francophile Arabs). Algerianism gains some scant support from the moderate left-wing, but makes little real headway on either the left or right; Moreau is admired by most of his colleagues, but can't quite bring them around to his way of thinking.
World War One comes as it did in OTL, with only a few trivial butterfly effects from the 1870 POD. In the fall of 1914, when the French government evacuates to Bordeaux, wild rumors spread of a second evacuation all the way to the safety of Algers. The rumors are groundless, and don't last long after the last shots of the Battle of the Marne, but they do help trigger a "What is Algeria?" debate in Algeria and, to a far lesser degree, France.
The aging Moreau, now a fixture of the Assembly, is an observer at the Paris Peace Conference, and is struck by two geopolitical trends that emerge in the months between the Armistice and the Treaty of Versailles. The first is the solidification of national identity in the self-governing Dominions of the British Empire. Australia, Canada and the rest, Moreau can't help but notice, sign the Treaty in their own right instead of letting London speak for them. The second trend is the siren call of Wilsonian self-determination, a call finding many receptive ears in Algeria (to say nothing of the vast French empire proper).
On July 28, 1920, shortly before his retirement due to the illness that will claim his life eight months later, Moreau delivers what will become known as the Three Roads speech.
"There are three roads ahead of Algeria. The first, universal franchise, an assimilation that is only pretense, an assimilation that will please no one, not in Algeria, and not in France. The second, total independence, which will throw away the blood and toil of generations. But the third, an Algeria that is free AND French - this middle road is the road to travel, the one we must travel if Algeria and France are to face the future, arm in arm."
The speech, although given with the elderly statesman's full power and gravitas, gets a mixed reception. Most French deputies from Algeria are die-hard reactionaries who refuse to consider any dilution of their control over Algeria, and their metropolitan conservative colleagues are only slightly less rigid in their thinking. On the left, Moreau's ideas find a positive reception with the Socialists of the SFIO while the Communist Party advocates Moreau's 'second road' instead of a 'Dominion of Algeria.'
It is in the 1924 elections that Moreau's dream is realized, at least in part. The French Prime Minister, Édouard Herriot, and his Minister of Justice, Paschal Berlo (a fellow Radical from Orléansville in Algeria), draft the famous (or infamous, depending upon your perspective) Herriot-Berlo Plan. This Plan proposed a significant expansion of French citizenship in Algeria, endowing it upon a large number of the Arab "elite" - university graduates, elected officials, army officers, and professionals. The Herriot-Berlo Plan is supported by moderate Arabs such as Ferhat Abbas as well as Moreau's faction of Algerianists while predictably opposed by most French-Algerians. Despite that opposition (vocally and violently expressed in Paris and Algeria), or perhaps because of it, the Assembly approves the Plan by a narrow margin.
With the stroke of Herriot's pen, the number of Évolués increases by a leap and a bound, with more to come, year after year - a nightmare for some, a hesitant first step for others. The wider world takes little notice of affairs in Algeria, and when the Black Halloween of 1929 sees the crash of the American stock market, triggering the Great Depression, little notice shrinks to next-to-none. All the same, the tide had been turned. In retrospect, the 1930s was the critical decade. The Algerianists or Franco-Algerians as they now call themselves, French and Évolué alike, had moved from the fringe to the heart of Algeria's political class, and increasingly spoke of Moreau's Third Road as the inevitable future for Algeria. The pied-noir establishment remains dominant, but ever-so-slightly less so as each year passes.
World War Two, like its predecessor, comes on schedule and at first unfolds almost identically to the WW2 we know. France falls to the Germans in 1940 and de Gaulle, in London, establishes the Free French Forces. And then history takes a slight detour - the Admiral in command of the French ships at Mers-el-Kébir is not Marcel-Bruno Gensoul but a French Algerian, Jean-Henri Dequenne. Dequenne scornfully rejects the "cowardly fossils" Petain and Darlan, and readily allies himself with de Gaulle and the British. There is fighting between Vichyite and Free French in Algers and other Algerian cities, but by the fall of 1940, Algeria is firmly in the hands of the Free French. Three divisions (two Algerian and one European) are raised and will later gain honor in Italy and Southern France.
To the Franco-Algerians, the 2nd and 3rd Algerian Infantry and 1st Algerian Armored divisions will be more than just a valiant part of the Free French war effort - instead, they are Partners in Liberation. To the Franco-Algerians, Algeria is a brother nation now, as Canada is to Great Britain. This attitude is far from a majority view, but it gains increasing strength among young Arabs and Europeans alike.
After the war, the debate about the form of the Fourth Republic is long and vigorous. As far as Algeria is concerned, the debate narrows down to two options - continuing as before, with the Europeans and a small (growing but still small) assimilated Arab franchise, or else adopting the Franco-Algerian notion of Algeria as a brother nation along the lines of Canada. When the French constitution of 1946 is passed, the Franco-Algerians prevail. (There is, no doubt, an element of pragmatism at work - letting Algeria loose, even a little, saves money that a war-ravaged France desperately needs for itself)
The reaction of the pied-noirs is quite measured and exceedingly discreet, and it only takes until 1950 before the last serious armed resistance is stamped out.
(And let's just give me sketchy notes for what comes next, pending the inevitable adjustments to all that above...
Algerienne units in Indochina, separate divisions under overall French command.
1960s Tough time, as another wave of settler conservatives fight against demographics and an increasingly politically active Arab population. Some Arab violence, allegedly supported by Soviets. Expansion of the franchise (just barely) avoids a full scale civil war.
1973 constitution, full emancipation for Arabs. Évolués remain the dominant voice among Arabs, at first. Settlers (initially) retain disproportionate numbers in Assembly (around 20%) but this soon falls to a more natural but still too high 10% and then steadily falls to around 7%.
1980s? Proxy war with Libya?)