Islamic Republic of Algeria
POD: Hitler's capitulation terms cause a major split the French government and a power struggle ensues. This results in Vichy France being unable to control any thing more than the European, Metropolitan France. In the OTL, the French government that surrendered went on to become the Vichy regime and they retain control of the colonies, at least immediately after the surrender. In my ATL, the breakoff government officials merge with the Free French authorities and the colonies, and Algeria, are under their control after the surrender.
Since Algeria is right across the Mediterranean from european France, Hitler flies in Algerian independence activists to discuss kicking the Free French government out of Algeria. He offers to send large amounts of aid to a rebellion, but no direct use of German ground troops. In late 1940 the Algerians rebel. Right on que, the Germans come to their aid. The Luftwaffe airlifts in a large amounts of weapons while bombing French positions. The armed Algerians manage to fully beat the rump Free French Army by late 1941. The Islamic Republic of Algeria is then declared. The local Pierd Noirs are repatriated to Vichy France. Internationally, it is recognized by the axis powers and their puppet states, so it aligns with the Axis, but mainly Germany. Algeria allows German troops to pass through as part of the North Africa campaign.
But the tide would turn shorlty after Algeria's independence. With Allies across the border in Libya, the Algerian leaders, who never formally declared war look for a way to stave off an invasion of Algeria. To the objections of France and Britain, the Algerians negotiate with the Americans. The two agree that Algeria would aid Germany no more, militarily or diplomatically, in exchange for no invasion. For the US, this deal is pragmatic as they do not have to waste troops invading Algeria when they have D-day and the invasion of Sicily to plan for.
For the time being, Algeria is spared. When the war is over, De Gaulle and subsequent leaders make lofty speeches about the illegal independence and that France will retake what was rightfully hers. Obviously France is in no shape to invade anybody after the war. So about 1948 France earnestly starts to prepare to invade Algeria. However Truman intervenes, and forces France to back down, going as far to recognize Algeria. The US had a post war goal of aiding decolonization. There's also the fact that a Western power invading another country opens the door to Communist support against the invasion. This backing down utterly humiliates France and makes US-France relations frayed going forward. Certainly how involved France would be in NATO from the get-go.
As the character of this state, given that it gained its independence due to German support, it could be acertained that this state is definitely not a communist one. Given that Germany's government was fanatically anticommunist, I would say that Hitler would help an anticommunist one come to power after independence. This anticommunist government would ipso facto be right wing and would develop close ties to Islamists. Hence the "Islamic Republic".
Going forward, Algeria would exist in a netherregion of the Cold War. Because of Israel and French dislike of their independence, they would be opposed to the West. But they are also inherently opposed to the USSR. Their only real allies would be their Muslim neighbours.