How do I determine an optimal or above average fee to gain priority in the network during a transaction? I am using the blockchain.info API to send btc from my blockchain wallet to about 3000 addresses. I'm using their send to many API/Service to do this. 

My problem is that I need to make sure the send doesn't get stuck or go to limbo. The amounts I'm sending are about 150USD to each of the 3000 addresses. 

The API call lets you set a custom fee to pay. What fee should I pay to gain priority in the network and ensure the transaction goes through fast and easy as possible?
The amount you should pay is constantly changing, so you'll have to check at the time you send the transaction. 21 has an API that provides recommendations on mining prices.

They are only recommendations though, there isn't really a definitive answer. The network could get flooded with higher fee transactions at any time, and your fee would then appear relatively low to miners. If you need to be absolutely certain you may want to raise the fee even further, but I believe they've taken some amount of that into account.