IMHO, it's not something that should change with difficulty..New recruits per month...maybe even the quality of recruits..
but on game start you should be presented with a good pool of soldiers. Why? So you can select those you like the best..Not only stat-wise but appeareance wise.
Maybe it doesn't sound important to some, but for some people it is incredibly important.
Now I'm the kind of player that will drop the Sword of Demons +30 and keep his Sword of Frost +5 if the Sword of Frost looks better 8and more functional) or simply "feels" better. (If I play a palading, no way I'm wielding a demonic sword).
Similar with every other game, I like to be picky with who I put in my team/fleet.
that's why I think a player should be able to either create at least 1 or 2 soldiers himself (set apperance and stats) or start with a bigger pool of soldiers. Let's face it - 8 soldiers to start with? For a elite, multi-government organization?