After many good answers and further research, it seems that, by all accounts, the Allies should have won, surprisingly enough. The Nazis won thanks to a ridiculous string of coincidences that would have had put any reader out of the story, had it be fictional.
At the end of WWI, France had the most modern army in the world. A massive pool of truck instead of reliance on trains for moving troops, the biggest air force of the planet, troops being equipped with semi-automatic rifles and a massive number of LMGs, turreted tanks and combined operations... And while Great Britain put comparatively more efforts into its navy, its army was about as advanced and had even started working on APC vehicles.
How do we get from this to such a debacle?
The post-WWI years
After war, both nations knew they needed a rearmament program, to thoroughly modernize according to the lessons learned form the war. Of course, rearmament programs are expensive, and when the deadly, exhausting, impossibly costly war that was supposed to be The Last One is just finished, some people may think that diverting funds sorely needed for reconstruction to the army is not the best idea.
In the aftermath, the British stop pursuing combined arms doctrines, which are slowly forgotten. And the general Estienne, father of the French combined arms doctrine, dies early before having time to further develop his ideas, resulting in the same loss.
tl;dr: Had either not let their armies decay, especially doctrine-wise, they would have been prepared against the new German tactics and blunt their advance.
Britain was focused on trying to hold together a dying Empire, and the focus on the navy and on rebuilding the economy left the army deprioritised, and it went back to a smaller expeditionary force, not unlike it was pre-war, even if its rearmament program was somewhat less disrupted.
Meanwhile, France starts its complete rearmament program. It develops a rather excellent light machine gun, then starts working on a new semi-automatic rifle and... thing peter out, especially after the 1929 crisis. Then new left-wing government, focused on social progress but openly contemptible of the traditionally right-wing army, cuts military funds as much as possible. A French head of state of the time goes as far as declaring that "If I could, the army would not get one centime in peace time".
Even worse, fearing the potential influence of the army, they change the appointment system for top officers: instead of picking from a list compiled by high command based on competence, they are now directly nominated, based on political affiliation. But wait, you might say, wasn't that exactly what had happened before WWI? Didn't France have to fire a third of its generals early in WWI because of that? Didn't they know that was a bloody stupid idea from experience? Yes they did, but remember, the priority was to make sure the army was not a political menace. And anyway, who would be insane enough to start another world way, after all?
As the threat of a new war loomed, France picked the rearmament program back up, but it was too little too late. They had great planes, but not enough - and the newest model was basically at the prototype stage and sent to the front from the factory. They had great defensive tanks, but with flaws not yet kinked out. They had great sub-machine guns, but only a few hundreds had time to reach the troops. They had great rifles, but had only time to equip troops with a bolt-action version planned for rear-echelon troops. The semi-automatic version, which would have been one of the best rifle in the entire war, was barely complete, and didn't even have time to leave the factory (fortunately, they did manage to hide its existence to subsequent German occupation forces).
tl;dr: Had the French government at the time not seen the army as a political enemy and cripple its high command, it could have developed new doctrines and efficiently respond to new German tactics.
The appeasement politic
Interwar France and Britain have been criticised a lot for their appeasement politic, believing that if enough concessions were to be made to Germany, they wouldn't do something as stupid as start another war. Had they read Mein Kampf, they would never have believed Hitler's words about wanting peace. (Then again, that book is allegedly so badly written to be painful.)
It is difficult to imagine what an early war would have looked like, but Germany probably was more unprepared than others. Had the Allies (possibly without Great Britain) gone to war over Czechoslovakia, it may have gone badly for Germany. But this would have required a significantly different political climate at least in France if not in Britain as well, so this is somewhat difficult to imagine it happen at that point.
However, had the Franco-Soviet 1935 treaty held, Germany would never had stood a chance in a war. Had Stalin compromised over not sending troops on Polish territory, or had France been less eager to appease Germany, the Soviet may have very well ended up with the Allied at the start of the war.
tl;dr: Had the alliance with the Soviet worked out, it would have been a race to Berlin five years early.
Speaking of Poland, they did quite better than is commonly believed (mostly based on Nazi propaganda, as it happens). But as to not, ah, provoke Germany, France and Britain had stopped Poland to fully mobilize, considerably hampering its war effort against German and then Soviet attack.
Even worse, its strategy was to hold long enough for the French army to launch an offensive across the Rhine, and for the British air force to launch a bombing campaign against Germany. Neither were actually prepared to conduct such operation, and had assumed Germany would be deterred simply by the threat. France launched a probing attack, met no resistance but decided to withdraw behind its fortification. Britain sent a few token planes, met no resistance but decided to stop further attacks. However, even unprepared (which they shouldn't have been), attacks against the undefended western Germany while its army was stuck in Poland could have stuck a heavy blow, either stopping it from finishing Poland or at least seriously weakening for the counteroffensive.
Also the offensive happened right before Poland would receive thousands of modern planes for its air force. I suspect Germany wanted to attack before that, as it would have seriously challenged the Luftwaffe.
tl;dr: Had the Allies been prepared to support Poland, they could have dealt a potentially fatal blow to Germany.
Defensive strategy
Nonetheless, as the years pass by, with more and more nations falling toward extremism, it had become clear that a new European war could happen again. The "twenty years of armistice", as Field Marshal Foch had called the Versailles treaty, were coming to an end.
Britain could count on the Channel, its navy, its air force and an alliance with several continental powers to prevent a war from reaching its homeland. France, however, was right next to the biggest potential threat, a revanchist Germany that could field twice as many men, and that had already proved its capabilities at massive industrial war. Which is why they did the logical thing and developed the Maginot Line.
But wasn't the Maginot Line a terrible idea that miserably failed? No, in fact it was a great idea and, when used properly, it worked exactly as advertised. (See below as for how it was not used properly.) It was the brainchild of WWI veteran Philippe Pétain who, despite some, ah, unfortunate political decisions later (again, see below), had still been one of the best generals of WWI - so not an idiot, and not an idiotic idea.
The Maginot Line was an impassable line of fortifications, estimated to hold with a contingent against an army fifty times more numerous. And, contrary to much later rumours, France was perfectly aware that the Germans would push through Belgium - and so was Belgium, in fact, which is why it was part of an alliance with France and Great Britain. Belgium was to build its own equally impassable Meuse–Albert line.
The problem is, impassable fortifications cost a lot, and Belgium simply didn't have enough money. So they asked France to lend them enough funds for the project. Which France declined (see above for why they would do such a thing). Which is why the Meuse-Albert line was delayed and scaled back. At the onset of the war, it was clear that the Belgian army wouldn't be big enough to hold a determined German push at its border.
tl;dr: Had France lent the money to Belgium, no German army could have crossed their eastern border.
Nevertheless, with the bulk of the French army and the British Expeditionary Force to back them up, it would still be enough to stop a German attack. As long as they were deployed in advance, that is. But if tensions rose, as allied nations, of course this is exactly what would happen.
But then the remilitarisation of the Rhénanie happened, and neither France nor Britain reacted, not wanting to declare war on Germany over internal troop movements. After all, they simply wanted to legitimately be able to defend themselves, right?
Belgium saw this appeasement politic as a sign that it couldn't count on the Allies, and thus left the alliance, hoping that neutrality would avoid it to be caught in the next war. Which meant not having foreign troops on its territory. Which meant that when Germany attacked, French and British had to rush from the French border to the frontline, losing much of their defensive advantage, and the easier to defend eastern Belgium being already overrun when they arrived. From there to Paris, there were only flat, hard to defend plains.
tl;dr: Had Belgium not left the Allied for neutrality, the German army would have been stopped, or at least considerably weakened, at its eastern border by the Allied forces.
But then, why didn't the French simply extend the Maginot line? Actually, they did. But two years were simply far too short a time to build such fortifications, especially on flat terrain.
The Ardennes gambit
Now, the German plan was to repeat the Schlieffen plan that had nearly worked so well in the previous war: launch a massive fast offensive through Belgium and run for Paris to knock France out of the war early. Sure, it had failed last time, but it had worked the time before that. And Germany didn't really have other options anyway.
At least, this was the plan before it fell in the hands of Belgian intelligence, when a German courrier plane randomly crashed in Belgium, carrying said plans. And while the Belgians tried their best to make it look like the whole thing had burned, the Germans knew to be better safe than sorry: they needed a backup plan.
So they did what would otherwise have been an idea worthy of the Chemin des Dames offensive in its utter stupidity: send two tank corps through the Ardennes forest.
Now, the French knew perfectly well that an Ardennes tank offensive was possible, and that a tank army could cross it in two days. Specifically, Maxime Weigand, possibly the most underrated general of the XXe century, had warned François Gamelin, the French chief of staff, of this.
(It was also Weigand that told Charles de Gaulle that his idea of a small, mobile professional army of a hundred thousand men for defense would simply not work - probably because the British had done the exact same thing during WWI and it had been ground down to oblivion in a few months, and thus earning De Gaulle's unending antipathy. But this is a story for another time.)
Once entrenched in the Ardennes forest, even a modest force could have stopped a tank offensive. Tanks offensives are meant for flat terrain: forests make it easy to ambush even big armored forces, and once a few tanks are burning on either side, can easily become death traps.
Unfortunately, as noted above, top officers weren't named for their skills anymore, and Gamelin was a courtier but not a good general. Which is how he ignored both warnings not only from Weigand, but also from French intelligence in Germany about their innovative light tank tactics and training.
tl;dr: Had Gamelin actually listened to his best general or his detailed intelligence reports, he would have easily destroyed the Ardennes tank offensive with a few well-entrenched forces.
But then, even without opposition, having two tanks corps cross a forest like the Ardennes is no trivial task. In short order, tank columns turned into giant traffic jams, easily seen by French aerial reconnaissance.
When receiving such reports, however, the officer in charge of defending the sector dismissed them as "a few scout cars". So the air scouts went back with tankers on board their planes, to identify the tank models and make unambiguous, detailed reports of the tank force.
No matter, the officer dismissed the new reports. When the French air force asked him if he needed any support, he answered none whatsoever. One may wonder if he was that incompetent, or if it wasn't actual treason. Had the air force been sent to bomb the piled up tanks, it would have been a massacre. The few survivors to make it would have been easily stopped by even a light force, had it been forewarned.
tl;dr: Had the officer in charge of the Ardennes defense not been terminally incompetent/a traitor, or had someone gone over his head (or executed him for treason), German tanks would never have made it out of the Ardennes.
The Battle of Belgium
The Belgian lines breached, the Allied forces on the back foot, and now a tank force emerging from the Ardenne to envelop them. As in 1914 the French government finally pulled itself together, fired the incompetent, politically appointed generals and let actually competent ones do the job instead and save the day. Namely, they pulled the aforementioned Weigand from retirement and gave him Gamelin's job as chief of staff.
Now, you would think Weigand was the right man for the job: respected by friends and foes alike, right hand man of Allied supreme commander Ferdiannd Foch during WWI, architect of the Warsaw Miracle, absolute légaliste with an unwavering loyalty to democracy and to the Republic. But with the entire French army disorganised, lacking radios and fast-moving forces, about to be encircled, what could even he do?
What he did, was to understand that the main German armored push was overextended, and that there was an opportunity: the French army would counter-attack in a pincer move, hammering the German forces against the British and Belgian anvil, and cut off the spearhead. British high command agreed with the plan, and so do modern experts, who argue that it would have indeed worked.
And then the British ran away.
Specifically, John Gort, commanding the British forces on the continent, panicked and ordered his army to rout towards Dunkerque - leaving behind piles of equipment for the Germans to take instead of properly destroy it all, but destroying bridges, trapping the French and Belgian forces that would be forced to retreat later.
With their flank gone, there was no more hope of victory for the French and Belgian forces, so they started to retreat as well. Both fought hard - the French fighting retreat was especially brutal, taking the highest relative death toll of all the European armies of the early war. German general Heinz Guderian, would in fact call the battle of Stone one of the two worse he ever saw - along with freaking Stalingrad. In fact, the one thing that saved the British army (along with Hitler's tactical mistake at Dunkerque) was the French army standing against literally impossible odds for the entire retreat.
Note: remember that next time you hear about a (much more recent) surrending monkey joke or about the Miracle of Dunkerque: the British ran and only made it because the French stood and died. Not even the guys who invented the Polish lance cavalry charging panzers myth dared to mock the bravery of French soldiers. In fact, Hitler himself called them the best in the world after the Germans (of course), in the aftermath of Bir Hakeim. But again, this is a story for another time.
tl;dr: Had John Gort not panicked and the British stood their ground instead, the German advance would have been smashed by a pincer move, stopping the German advance.
For what of a fistful of nails
Had the German advance been blunted, things would have reverted to a 1914-again state: a grinding war with neither side capable of advancing. This would have pitted industrial and manpower reserves against each-other, and like for WWI, the Allies would have had the upper hand with access to the immense American industry. The Soviet Union may have somewhat balanced this by trading with Germany, but this is neither certain nor guaranteed to have lasted. (Soviet-directed Communist agents were executed in France for sabotaging planes, for example, so the Soviet Union was, at least initially, somewhat serious about their pact with the Germans.)
New weapons would have made a difference. Many northern French and Belgian cities may have been razed by artillery fire. New railway trains may have been used to destroy fortifications like on the Maginot line, but the enormous investment on those and on the follow-up force needed to have a chance to advance. As such, like in WWI, it is improbable (though not impossible) for the Germans to achieve victory that way.
In addition, and contrary to what many think, the Allied had the initial technological advantage. In fact, the reason later German tanks were so good was partly because of the French tech they got their hands on, and on the resources of the French had from their colonial empire, allowing for better alloys. Had the war become static, the Allies would have kept the technological advantage, especially with Hitler increasingly obsessed with wunderwaffen and the French armament program being finally completed and extended.
Given how fast it rebounded after the war, and as there were pre-war projects already, France may have been the first one to develop rockets and even jet engines. it may even have fielded ramjets, whose development were interrupted by the Occupation. They also had few wagons full of uranium ore that spent the entire Occupation pointedly forgotten in some railway depot, but while it would have considerably helped nuclear development, it is far from certain that the war would have lasted long enough for an atomic bomb to be finished.
tl;dr: Had the initial push been stopped, it is improbable that Germany could have won WWI-bis.
Aftermath
At this point, the French homeland was lost. There was next to nothing left between the German army and most of France, with indefensible open terrain in the way. But France was still not ready to give up. it had 150 000 surviving troops evacuated from Dunkerque. It had an army holding the Italians at bay in the Alpes. It had an oversea empire, from which colonial troops could be raised. It had a modern, rather powerful navy.
So the French government did the sensible thing, gave up the indefensible territory and prepared to move the capital to Algiers (as Algeria was considered more or less French homeland at the time). In this time of crisis, they decided to unearth this old Roman tradition: nominate an emergency ruler with dictatorial powers, so the slower democratic powers can be temporarily been bypassed for the duration of the crisis. After all, if it worked for the Romans...
So they chose the victorious chief of staff of WWI (Foch was the supreme commander of the allied forces at this point, which was not the chief of the French army), the Lion of Verdun, a national hero whose military skills had been well-proven: Field Marshall Philippe Pétain.
Unfortunately, he was also going senile and had never liked politicians to begin with. This was the "divine surprise" that fell on the lap of the far right, who seized the opportunity to take power in Pétain's name and stage a coup d'état. While officially called the "Nation Française", it would be remembered as the Vichy regime. In short order, being ideologically close to Germany and Italy but deeply anglophobes, they would sign an armistice (not a capitulation, because that would make the army lose face, a big no for a fascist regime) and nevermind the loss of half of France and basically becoming a puppet of Germany (even if officially neutral in the war).
Oh, remember the French navy? half of it was stuck in Toulon and, much later, scuttled itself so the Germans wouldn't get their hands on it. Another half was in Mers-el-Kebir, and the British murdered it with a surprise air attack, so (agian) the Germans could't get them - but the French sailors were actually busy scuttling said ships, so not only were they especially defenseless against a surprise attack from an ally, but even more died trapped in the ships.
So while the armistice was very unpopular for many French, many also felt betrayed by the British and decided that neither side was worth it anyway. Even then, and despite everyone (including the Allies) considering the Vichy regime as the legitimate French government, "Fighting France" (later Free France) was formed as a government in exile refusing to stop the fight. While only a few troops and colonies joined it, plus those forming Résistance groups in Vichy and occupied territory, they became increasingly popular and, in the case of Bir Hakeim, even instrumental in the war. But again, this is a story for another time.
tl;dr: Had the French government named the maybe too modest Weigand instead of Pétain, the French Republic would have kept fighting from Algiers.
And the Devil is laughing still
Now as this is Worldbuilding and not History, let's try to make sense of it. Because as it is, this is all too ridiculous to use in a story, nevermind that it actually happened.
So let's take this ridiculous chain of coincidences, and the fact that it suddenly started to fall apart everywhere. Add the countless failed assassination attempts against Hitler. Add that the Nazi regime was not simply evil, but Evil. They didn't just invade Europe, raze cities and murder countless civilians. They didn't simply have insane racial theories they actually attempted to put into practice, and allied with an equally monstrous regime on the other side of the world. But not only did they industrialize genocide (and yes, I am the first to be surprised that it has to be reminded nowadays), but they actually wore skulls as a symbol.
And the SS had a war song with those lyrics (translated, obviously):
"And the Devil laughs with us"
"Ha! ha! ha! ha! ha! ha! ha!"
Also Hitler was into occultism.
tl;dr: there is one obvious explanation: Hitler made a deal with the Devil.
Seriously, why don't more people use this in secret-history or alt-history works?
