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.