If I sit down for a set, and I have become the elector of who will go first, do I know the size of my opponent's deck when making this decision? Could a player be keeping that deck in a big box at the time we flip the coin and I make this decision?
If it is a multiplayer game, I surely know the seating arrangement we have before choosing the Starting Player, right?
The rules make clear that the choice of the Starting Player happens before decks become libraries, or undergo shuffling, but it is silent on whether the deck or deck list has been presented. My reading is that not; though I can count a library, the deck does not become a library until after the initial shuffle.
But regarding seating order, even though there are rules for multiplayer formats defining methods that may be used to pick the seating order, I do not see where they say that this order is available when picking the Starting Player, nor that it is unavailable. For example, Grand Melee defines the seating order is decided to be random (807.3), but does not relate this to the game setup procedure.
103.1 and 103.2
The game begins by shuffling up your decks and choosing who goes first. In practice, most players do these together, rolling a die in the middle of shuffling or similar, but the rules have to say which happens first, and shuffling was chosen sometime in the past. Companions make it matter which happens first, since we need a starting player before setting aside cards before shuffling. Determining the starting player always comes first now, though, if it doesn't matter, you can keep on doing whatever you were doing all along. (How often do you really want to pick a companion based only on your opponent's?)
So it does seem yes, it would be possible to flip the coin first, then have some player bust out a large, unknown deck.
For the seating arrangement though, I found this:
800.5. Unless a chosen variant or option prescribes otherwise, seating order is determined by any mutually agreeable method. For example, players could agree to remain where they were before the game began, roll dice to determine seating order, and so on.
And I'd say that figuring out the timing for this falls under the mutually agreeable portion.