I like them to start with Russia. Tanks and infantry are much easier to deal with than with all the units like Japan.
Start them off by saying, “Bill is your ally. You really need to listen to him until you get a feel for things. And that will take about 2 games.” The first game is always a wash. Always tell the new guy that the first game is just for fun. Because, really, they need to get through it to get an idea of the end game.
Also, I like to play 2 rounds and then reset. Then play Russia for at least 2 games, but preferably 3. It’s up to them at that point.
And it’s important to guide them while letting them make decisions. Keep things simple. New guys don’t need to know the intracacies of every unit type during the first turn. Set them up for the standard buy, and move on with life. Tell them what moves to make and let them roll the dice (because until they understand how combat works, they can’t understand what units to commit to battle, or buy, or even where to place them).
But again, I think it’s important to keep things simple. Don’t explain EVERY battle the other players fight. Of course, use the other battles as teaching moments. Show them the rule book and show them how the rules apply. “See, it says here that enemy subs can be ignored if there are no enemy surface ships.” And, “See how fighters start their movement independent of their carrier. See how they can move three spaces, fight, and then back one, and land on their carrier?” Just don’t pile on rule after rule.
And for several games at least, don’t let them make stupid mistakes. It’s no fun to win because they didn’t understand that bombers can fligh across the US and attack un-escorted carriers in the middle of the Pacific.