How many shots should one take to get a reliable estimate in a quantum program?

This is depends on what algorithm you are executing.

For example, if you look at the Bernstein-Vazirani algorithm then theoretically the number of shot you need is 1 if you have a perfect quantum computer. This is because the end result that you are looking for collapsed onto a single eigenstate. However, because of noise, we would like to do more. In term of how many more, this is depends on the device. Not all device have the same noise level. You can, actually, look at the gate fidelity on the machines (at least you can do that for IBM's machines) and work out the probability that your circuit will fail, then from there determine the number of shots you might want to use. However, without doing that analysis, then you can just be on the safe side by using the maximum number of shots giving to you. For IBM's machines this works out to be 8192 shots. However, you can run multiple jobs to collect the statistics if you think you need more shots than this. Now, of course, if your quantum circuit is too long, the errors will built up so much that your circuit will "essentially" guarantee to fails, then additional shots will not help.

The above discussion is for quantum algorithms that only need $O(1)$ shots/samples. This is not true for algorithm like VQE. For VQE, we need to do $O(1/epsilon^2)$ shots to achieve error of $epsilon$. For chemical accuracy, which is for $epsilon = 10^{-3}$, you would need to do ~$10^6$ shots at each iteration... which is insane!

Now if you just create a random circuit, which output a state that could be in super-position of $2^n$ eigenbasis then you will need $O(2^n)$ shots to able to able to extract the output probabilities. This why, designing a quantum algorithm is like an art. Therefore, You can't just do some operations on a quantum computers, and claim that because you did it on a quantum computer, it must be faster than doing it classically. You do not have access to the state of the qubits! This is also the reason why you can't just perform Quantum Fourier Transform ( essentially doing Discrete Fourier Transform on a quantum computer) and claim that you have a speed-up. Although, QFT does give you an exponential speed-up over DFT or even FFT (Fast Fourier Transform), doing it randomly will output a generic quantum state that in superposition of $2^n$ eigenbasis... Extracting out this state would take exponential amount of samples which then defeat the entire purpose.