When running a service that needed a bitcoin address, would it be better to generate a new address to use at that moment and store the private key on your server, or would it be better to pre-generate say a million addresses and have the private addresses already stored offline?
The later would be combined with a backup option to generate on the fly if its address pool dried up.
To answer this question accurately, we'd really need to know more about how these new addresses will be used in your service.
If these newly-generated addresses are to be "deposit only", that is, as long as you're not needing to send coins from these addresses, then the most secure option by far is to generate the addresses offline and keep the private keys offline. This is pretty obvious: cold wallets are almost always more secure than hot wallets.
Unfortunately, most services will need to access the private keys of newly-generated addresses for some reason, if only to send any Bitcoins received to another wallet. In this case, the next best option is to maintain as low a balance as possible in these addresses. That is, as soon as they receive any coins, forward the balance as soon as possible to an address that is stored in a secure, offline wallet.
If you can limit yourself to only use pre-generated addresses for receiving Bitcoin payments, then that option is clearly preferable because it significantly lowers your server's security requirements, from having to protect a secret to having to protect against the injection of bogus Bitcoin addresses. Even if your service involves more than just receiving Bitcoin payments, handling only the Bitcoin addresses is the safest option for your web servers. Of course it only shifts the challenge of securely handling the associated wallets, but it allows you to separate this task and hence gives you more flexibility. For example, you may find a particularly cheap way to run a bitcoin-handling server on your own premises but without the connectivity to act as web server.
If you want to reap this security benefit, then you should not fall back to generating new addresses on a server meant to not handle wallets. Instead, you'd need to limit your usage of them such that they won't be used up before you can replenish them. One option, of course, is to pre-generate a huge number of Bitcoin addresses such that hardly any rate-limitation is required to prevent you from running out.
