Let's say I want to make a large transfer to an exchange. I am sure to verify the receiver address. However, if the exchange made a mistake somehow, all the bitcoin would be lost forever. So does it make sense to send a small amount first, confirm that they receive it, and then send the rest?
Because I have also heard that each address should not be used more than once.
Sending a small amount first is not a bad idea. It is unlikely that there will be a problem with the address but it will test your ability to send correctly.
When you receive bitcoins you should use an address once. However, the exchange is receiving the bitcoins from you in this case, so it doesn't matter.
On the other hand, I change deposit addresses occasionally. If my deposit address can be associated with me, someone could potentially track the amount that I deposit into the exchange. Changing the deposit address makes that more difficult.