If I use two change addresses to make a transaction to another wallet of mine, then it would be clear to everyone on the blockchain, that these change addresses belonged to the same wallet, no?
Yes.
Wouldn't I have double the transaction costs, using two addresses?
No.
The amount of addresses you use doesn't matter.
What makes a transaction large in size is the amount if UTXOs used.
If you receive X transactions to the same address of type Y, then you'll need to pay the same fee as if you'd receive X transactions to X different addresses of type Y.