How is a large, spread out company supposed to work with the iOS Developer Program?

A $99 "company" developer membership allows the administrator of the account to set up many "developer" accounts. You should get the administrator of that account (whoever set it up originally, most likely) to create accounts for each of your developers.

You might need to share the admin account for things like provisioning and app submission, but for most of your daily work, you can have your own login that shares the developer membership.

Since Apple has spoken that each "company" only gets one developer program, you will be forced to share or create a new company.

The initial burden of forming a wholly owned subsidiary for the purpose of establishing a legal entity is something that independent developers do for less than $500 and they get professional, but canned help.

You'll have to run this by your finance and legal teams to know how painful this will be for your company's particular situation. It's fairly simple for an individual to have an LLC or S corp fall under personal income tax and handling the filing paperwork with the state government is more of a light administrative burden. It could easily be more costly and complicated for a real corporation to set up a child company - but that's the direct route to getting your own developer account.