If you're looking for something Maximilian himself could have done differently, either make the concessions to Juárez even better, or withdraw them once Juárez rejected them. Every other major choice he had seems like it would be too little, too late.
But the biggest factors in his defeat all come down to the USA: Lincoln's open secret program of "losing" munitions at El Paso del Norte, which evolved into Johnson openly arming Díaz's partisans; Seward's hardcore diplomatic pressure on France to withdraw and other countries to stay involved (according to Empress Charlotte, although this may have been partially paranoia on her part, "Everywhere I turn for aid, Seward has been there first, and doors shut in my face"); rumors that Johnson was seriously considering an invasion on behalf of Juárez… there's just no way to win with all of that happening. So, the key is to keep the USA uninvolved.
The easy way is to just push the Civil War back a couple years; by 1867, the Empire could plausibly have been a fait accompli.
The more interesting way is to change US interests just enough to prevent that involvement. Which is challenging, but not impossible.
It all starts with the Cotton Embargo.
In April 1861, the CSA began a voluntary embargo on cotton exports. The theory was that this would drive Britain and France to the brink of a depression, they would blame the Union blockade, and sweep the seas of the Union navy. The historical result is that it was laughably ineffective, and only managed to mildly annoy the French.
The first problem was that the CSA started the embargo too early, before the Union blockade was even set up, so nobody would have blamed the North if there were a problem. Leave that the same in your history.
The second problem was that France had their second year in a row of massive crop failures, meaning wheat and corn imports from the North were far more important than cotton. At the same time, England's Egyptian cotton plantations had a bumper crop, and were able to massively expand operations.
Reverse the two, and France really would have faced serious economic hardship, and blamed it entirely on the CSA.
When Seward makes his declaration that anyone who aids the CSA is at war with the Union, instead of ignoring it (but doing little to aid the CSA), Napoleon III, to spite the South, wholeheartedly agrees, and insists that all European states remain neutral.
Instead of spending the rest of the war alternating between veiled and open threats to keep Europe out of the war, the US State Department begins cultivating friendly relations. When France has a crop failure in 1862 instead of 1861, Seward takes advantage of the trade agreements to strengthen the positive ties. Of course the French still aren't going to back the Union, but their diplomatic position is far more pro-North than it would have been, and that carries a lot of weight in the rest of the Europe.
- By 1863, rather than unilaterally declaring a Mexican Empire, Napoleon III encourages Maximilian to bring the USA in to arbitrate.
- Being still busy fighting the Civil War, there's little the USA could practically do if they turned this down, so they accept.
- The Seward Compromise is Juárez as Imperial Prime Minister, and a pledge to continue his social programs (that Maximilian wanted to continue anyway). In exchange, both France and the Union pledging to support the compromise government, and France promises only limited troop deployments.
- A group of Maximilian's Conservative backers announce they will withdraw support if he agrees to it—but he agrees anyway.
- Now it's down to Juárez. It's basically the same deal he turned down historically—but getting the deal from the USA rather than from Maximilian makes a big difference, and Maximilian being more cut off from both native and French support makes it a lot easier to trust him to keep to his side.
- Juárez, despite being reluctant and wary, sees it as the best option, and signs.
- Juárez gives a famous speech, known as Los Cien Días, asking the people to give the new government 100 days before passing judgment.
- Porfirio Díaz refuses to join the government, or to merge his army with the Imperial army, but agrees to the 100 days.
- For 50 days, everything seems to be going well. Maximilian keeps his word, allowing Juárez's reforms to continue. Napoleon III keeps his word too, sending only limited troops.
- Then comes the Hacendado Coup. A group of Maximilian's original strongest supporters, together with some retired French and Austrian officers, capture most of Mexico City, and announce the dissolution of the government. They claim they're doing this for the benefit of the Emperor, but Maximilian announces that he remains faithful to the government, and calls on all of the people of the Empire to support him.
- Díaz quickly moves to retake the city. The French troops, after a tense standoff, withdraw to the port to avoid taking sides. Díaz quickly restores order, and Juárez welcomes him in the name of the Emperor.
- A few months later, the American Civil War ends, and Lincoln is shot. Johnson isn't very happy with the Empire next door, but there's not much he can do about it. Maximilian and his government are successful and popular, the key revolutionary figures have been co-opted.
- The USA begins a policy of trying to sway Mexico closer to their side, but it has little effect. While Mexico does drift away from France, especially after the Third Republic is declared in 1870, the main beneficiary is Austria.
- In 1900, after a long and mostly successful reign, Maximilian is succeeded by his nephew, Otto Franz.
- In 1914, Emperor Otto I's older brother Franz Ferdinand is assassinated, and Mexico is the third country to declare war on France.
- In 1917, Germany decides it needs to resume unrestricted submarine warfare, even though it will probably draw the USA into the war. Their allies in Mexico preemptively declare war and launch an immediate invasion.