The more I think about the issue the more I am convinced that reducing to 4 will not solve the general problem of predictability. Knowing the number of initial armies per starting territory is inherently predictable and encourages static opening strategies. Fixed values are boring, no matter if 5 or 4.
Suggestion I:
Why not have both?
Let the 1st picks remain 5ers and 2nd and 3rd 4ers. In case you don't get your 1st pick the 5er moves over to the 2nd pick, of course. So 5-4-4 would be the distribution. Or 5-4-3 maybe? Might be interesting as well?
Suggestion II:
Why not have an addition step after territory picking?
1) pick territories, each territory starts with 1 initial army.
wait for all players.
2) distribute an amount of xx armies freely among your starting territories.
wait for all players.
3) continue with turn 1
2) and 3) could be combined if desired, of course, basically I'm suggesting to give a one time amount of xx additional armies for distribution on turn 1.
Suggestion III:
Let players pick territories and distribute armies simultaneously. Then let the distribution of armies decide who gets which territory, not the order of picks.
So if someone so desperately wants Central America he can make sure he gets it by placing most of his reinforcements there, at the cost of lowering priority for his other picks.
Players should be able to distribute more armies than they actually get, since they also can pick more territories than they actually get, but the total they receive will not exceed an amount of xx armies. Players spending less than their maximum amount of armies get those left over armies for distribution in turn 1, so all have the same numbers.