What happens if a SegWit address sends BTC to a legacy wallet address (and vice versa)?
You can send
from a "bc1" addresses to any type of address (legacy or segwit) just fine... the *ONLY* issue with "bc1" addresses is that
some wallets and online services do not yet recognise "bc1" addresses as being valid bitcoin addresses. So, if you attempt to withdraw coins from "StupidExchange" to your "bc1" address, the StupidExchange will refuse and say your address is invalid
In this instance, you would need to either... use a "nested" SegWit (aka P2SH-P2WPKH) address... these start with a "3" and are backwards compatible... all wallets and services should be able to send to this address... or you would just use an old legacy address (starts with a 1).
And...Are people able to create NEW legacy wallet addresses? Or are they only able to restore legacy wallets that were created before the SegWit update?
Yes, you can still create any type of address/wallet that you want... Legacy ("1-type"), Nested SegWit ("3-type") or Native SegWit ("bc1" aka bech32)... assuming of course that your wallet software or provider supports that address type.
Electrum has ways to create all 3... so does Bitcoin Core... some only support Legacy and Nested.
The legitimate exchanges that you send a nested segwit transaction to (from the address beginning with bc1) will be able to add your funds manually within a few days after contacting support.
That should be "native"
And it shouldn't make any difference to the exchange what address the transaction came from... they should only be concerned with outputs... so they should see the newly created UTXO just fine and you shouldn't need to contact support at all.