If I understand correctly, there is a second Merkle tree of witnesses mirroring the transaction data. The witness tree's root is committed to in the coinbase, but otherwise this second tree lives outside of the block.
That is my understanding as well.
Don't the witnesses still have to be relayed to other nodes to validate?
Only nodes that actually care about the signatures. There are thousands of SPV nodes, for example, that want to be able to calculate the TXID of the transactions they care about but that don't actually need the scriptSigs other than that, since SPV nodes rely on confirmations for security instead of fully checking scripts.
Why is it acceptable now to send more data, but raising the block size was dangerous, and exclusionary of nodes on slow connections before?
Many people rejected the idea of increasing the block size limit simply because it was a hard fork. The extra data and exclusion of some nodes is still an issue, and I'm sure there will still be plenty of arguments about how to count the witness data. This just eliminates/postpones the hard fork max block size debate.
Pieter Wuille's current proposal is to give a 75% discount on signature data, increasing the effective max block size to about 4 MB in the worst case, but that would probably never come close to being realized in any normal, non-malicious, circumstance. I would estimate that a full 1M normal block would be a 1.8 MB block of completely SW transactions.
Also, if witnesses are outside of the block and prunable, how will a fresh fully validating node get up to date? If a smaller subset of full nodes hosts all witnesses, does that trade off security for amount of transactions in a block?
When a full node comes online now, it currently doesn't even check the script evaluations in anything older than the most recent checkpoint. In this sense, it's not a 'fully validating' node, it's more of a 'fully validating from 6 months ago onward' node. But, unfortunately, to build the UTXO set right now you still need to download the scriptSigs, even though they're not used for any validation. The Segregated witness change makes it so that in the case of SW transactions, excessively old scriptSigs that wouldn't be verified anyway don't have to also be downloaded, because the TXIDs don't use them.
Note that some transactions using Segregated witness doesn't magically make old-style transactions more prunable, unfortunately. However, if Segregated witness were fully in use by all transactions today, then in 5 years from now, a node that was getting up to sync wouldn't have to download a lot of the signature data from the past 5 years, just the most recent signature data.
So, there is a security trade-off there, but it's the exact same trade off that already exists. With SW, though, you just have to download less data (~60% less of the new SW transaction data) for the same security.