...
I tried using a legacy address (The one that starts with 1) and I got a different error message: The address provided does not match any private key.
Then you are attempting to sign a message using an address for which your wallet does not contain the matching private key.
Where did this address come from? Did you generate it using your Bitcoin Core wallet? If so, how did you generate this address?
If you didn't generate it from your Bitcoin Core wallet, then follow
hosseinimr93's advice and generate a legacy address from within Bitcoin Core, then sign a message using the newly created legacy address.
Or get the private key from bitcoin core and import it to Electrum(As temporary) and make a sign message.
That is a terrible idea. Private keys should not be exported/imported without a very good reason (like last ditch attempts at fund recovery etc)... exposing one simply to sign a message is a terrible reason, imo.