That's a great question. I never noticed that the setup rules only list the top three in the line of succession. We have always played as if the full line of succession were in play there. So in your example, the admiral would be Apollo. Not having an admiral (or president for that matter) would cause some significant game play issues. I have to assume the intention was to always use the full line of succession. So I would say, yes, someone always has to be admiral.
In the base game, the only way this can happen is in a three player game where someone chooses a support character, i.e. Tyrol. I think this was an oversight in the rules. Without Tyrol, it would be impossible for this to happen, because someone would have to choose one of the three military leader characters.
If you follow the rules-as-written, to the letter, it could be even stranger in a game including the Pegasus expansion. Cain is first in line of succession, but I don't believe anything in the rule book technically modifies the rule you mention on page 5 of the base rule book. So if Cain and Helo were both selected, a literal interpretation of the rules would give the admiral title to Helo. Clearly that isn't the intent. I think the obvious answer is to always refer to the line of success lists.