Historically, the Germans failed Operation Barbarossa. The soviets never crumbled during the operation, they were hard to battle against. They were very good at defending and they would fight harder, and to the death, more often than any other armies would have. This was all stated by the Germans during Operation Barbarossa.
The reason why the soviets were pushed back a lot was because of poor leadership, command and control being destroyed, communication being sabotaged and of course, complete surprise. Not because the soviets were not hard to fight. Whenever the Germans had to engage in battle, it was a hard battle. Take for exemple the Brest Fortress where it took the Germans about 7 days to capture.
Its completely normal to have difficulties fighting the Soviets in the game. What makes it easy to destroy them is how,when and where you move your troops. This is what got the Germans trough the gates of Moscow.
Play the game and test it out a lot. The Germans had wargame and had lots of opportunity to recreate Operation Barbarossa before engaging the real thing. It was originally planned to have one panzer army from AGC to assist in the capture of Leningrad, meaning that two panzer armies would be operating in the South. But the wargames had showed that this was not the best course of actions.
Lots of the original plans for Op. Barbarossa were changed after playing the wargames. You can do the same. Play the frontier battle over and over again until you get good and you know what works and what doesn't.
Try different approach, think outside the box.
I have a full playtrough ( of the frontier battles ) where I dont use my Panzer groups AT ALL. Just because I want to save them for October-November-December. I used my mechanized divisions only. ( I do not recommend this tactic however ).
Just try a lot, and play a lot. I have never made it close to Moscow myself, and have about 100 hours put into the game. But I get trough the Frontier battle pretty easely now and in a timely fashion. I need to practice my strategy for the late game a bit more.
What I found out work best is to drive 2nd Panzer group into the Pripyet marshes, along with 4th army HQ all the way to Gomel, once this is done, I use 4th Army HQ to hold and defend the Dnepr river from Mogilev to Gomel. while I shift 2nd Panzer Group into AGS. By the time I arrive in Gomel (with 2nd ) and Mogilev-Gomel line ( with 4th ) ( this is done in about... 3 or 4 turns ). My armies in the South have connected with 3rd Rumanian HQ and have a static defense line from Lvov to Proskurow to Odessa ( Odessa might not be captured just yet though ).
So 2nd Pz.gr will make their way to Kiev ( usually garrisoned so I skip the battle ) and then I continue to Rovno and Zhytomyr. 2nd Pz.Gr Infantry at this time is usually still in the marshes, so I make them walk from the marshes directly down to Rovno. Effectively closing the kessel. What happens here is you have about 1 million Soviet stuck in that Kessel in about 5-6 turn of the start of the game. Nevermind all the other kessel you created with AGN and AGC while you were working on that one, you should have about 2 million Soviets in your Kessels, either already destroyed, or on the verge of.
That creates a big blow, the only difficult choice at this point is where to advance. Because everything is left undefended ( apart from Garrison ). You can go to Kiev,and Kursk almost without danger of seeing enemy troops. Or you can use your newly freed 1 Pz.Gr to drive to Odessa and capture it in a lightning fast. Creating another kessel between 11th Army HQ and your Panzer Group.( if you are going for this, the trick is to not move your Southern armies at all apart from 17th Army, 6th Army and 1st Pz.Gr. That way you can capture more Soviets. You can then drive to Rostov without seeing much enemy troops.
I usually bring 2nd Pz.Gr back to AGC. At that point, you will need them as you will be struggling in the Center. Drive them to Smolensk, and make a kessel 3rd Pz. Gr. You will have another huge pocket of Soviets trap from Minsk ( where your infantry will probably be stuck fighting while you go south with 2nd Pz Gr. ) to Smolensk. This adds another 500,000 soviets to your kessels. At that point you have about 3 millions soviets eliminated and its abouty turn 10 to 15.
Of course, there is an alternative choice, instead of going South with your 2nd Pz Gr. you can stay center. When you get to Gomel, there will be no one in Smolensk. apart from Garrisons. Drive to Smolensk and meet with 3rd Pz Gr. who will be waiting for you in Polotsk. This creates also a huge kessel in the Minsk-Smolensk area, and makes you ready for a drive to Moscow without much resistance ( although, I never yet tried this strategy, but I have thought about it and planned for a while now that I think I am ready to try it soon )
The trick with this game is to plan ahead. Before you even start turn 1 you should know what you are about to do. Choosing Hitler's Directive might be easier on PP, but it can get way easier if you choose to capture Rostov and just completely annihilate the armies in the South with your two panzer groups. Or if you chose to go Moscow, then you would stay in Center and make the Smolensk-Minsk kessel.
Dont just go turn by turn, advancing everyone as the game goes. This is when you create a Verdun type of game. Because you havent planned anything, so you cant move your troops according to your plans. I bet this is the reason why most people dont succeed.
Now dont get me wrong, I didnt get to Moscow myself, just yet, but this is how I used to play the game, without planning ahead. Now that I started to plan ahead and think about my strategies, I started being way more successful. Such as capturing over 3 millions soviets by turn 10-15. With about 200,000 of my own casualties.