I like to start all of my games in the '36 Scenario, gives you lots of choices of how to run the course of history.
I've played (with sucess and with failures) countries like Germany, France, England, USA, USSR, Norway, Sweden, Finland, Yugoslavia, Romania, Austria, Poland, Italy, Japan, Nat. China, Comm. China & Spain (can't remember if there are others that I left out, South Americas I think I've played Brazil & Argentina, though it could be HOI1 I'm thinking of)
Edit:
I missed the point somewhat, of all the countries I've played, I think Germany is still the best to start off with. You gain experience by managing your policies in politics, research, troop managing, etc.
By the time WW2 starts, you will have a good grasp of the mechanics of the game.
Win or loose, your next game will see you give the AI a good run for their money.