If I have a wallet/address with 1BTC in it, how can I distribute it to 1000 different addresses (1k new addresses with 0.001BTC in each), paying the least amount of transaction fees? Sending 1000 near-zero-fee transactions and hope that they all get through in an "acceptable" time is an option I guess, but are there any other options?
The best/cheaper way to split a single address into multiple is using batching transactions:
This blog post from David Harding shows what are the saving possibilities when using batching to send your transfers and how it works:
Samourai Wallet supports batching if you don't want to use api's.