The primary difference is that 出す implies something sudden or unexpected. For example, consider the sentence 私は泣き出した and 私は泣きはじめた. In the first we get a natural expression which implies that you (beyond your control) started crying. The second one is grammatically correct, but by using 始めた you're implying a sense of purpose, like you're making yourself cry for some reason. You cannot use 出す to express will or volition, so the sentence 歩き出しましょう would be strange.
The tricky part about trying to find a distinction here is that no matter how many rules you try to apply you're going to be finding exceptions. At the very basic level you can think of 出す as something unexpected or sudden, possibly both, possibly just one. I'm going to borrow a citation from one of the pages below:
I agree with the bit that suggests a slight surprise or confusion, even in situations like スタートの合図が鳴り、彼らはいっせいに走り出した。 Even if you expect them to start running, there's still an air of unexpectedness to it because the signal comes suddenly. 出す suggests that they were still and suddenly started moving. If it were 走り始めた then it would have the same general meaning but that nuance of sudden change is gone.
Also just to briefly mention it, 出す also has a spatial meaning of movement from inside to outside, like in ポケットからナイフを取り出す, but that's unrelated to the sense of beginning.
As for your other points, I don't think there is a real difference in formality. I can imagine both being used in formal speech as long as the occasion calls for the nuances associated. You mentioned the part about deliberateness and control which is correct for 始める in some situations, but it's important to note that it can have general connotation of expectedness when it's out of the control of the speaker, like 太陽が沈み始める. And I agree that there is more of an emphasis on the 'beginning' of an action with 始める while 出す tends to express more of the sudden change between two states.
Check these sources out for more info: