My searches are indicating this could be because Electrum is generating a certain kind of "Segwit" addresses, which exchanges do not like sending to. Is this the case?
In a word, Yes.
Have I gone down a blind alley using a format that is going to be incompatible with everything else?
Not necessarily incompatible with
everything... it is just that some services have not yet included "bech32" compatibility.
Would I be better off starting from scratch with a different wallet?
For a beginning user, the 'safer' option is either a Legacy wallet (creates addresses that start with a "1")... or perhaps a SegWit wallet that uses the P2SH-P2WPKH system that generates backwards compatible addresses that start with a "3".
Unfortunately, Electrum does not offer creating a P2SH-P2WPKH type wallet without a bit of manual work (
you need to restore a wallet using a seed mnemonic, check options, select BIP39 and then select the "p2sh-segwit" option)... As per the linked guide, doing this using an Electrum generated seed mnemonic is arguably a "bad idea"™ as they are not BIP39 compatible, so you're using the mnemonic in a non-standard way which
may cause issues later.
One way to mitigate that, is to simply generate a BIP39 seed mnemonic using a different (BIP39 compatible wallet), and then import that BIP39 seed into Electrum.
The 3 different address types have a few pros and cons, but in simple terms:
"1-type" address - Legacy bitcoin address, supported by everything... creates larger transactions that can cost more in transaction fees if the fees spike
"3-type" SegWit address - P2SH-P2WPKH, backwards compatible, supported by everything... creates "smaller" transactions as it benefits from SegWit
"bc1-type" SegWit address - "native" SegWit, NOT support by all wallets/services, but offers the full benefit of SegWit and generally lowest transaction "size"
NOTE: there are non-SegWit "3-type" addresses... just to really confuse things!