Generating addresses on the fly or pre-generate and store public key? 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.