For distributed multi-user and multi-relay cooperative networks, the received signal may be affected by multiple timing offsets (MTOs) and multiple channels that need to be jointly estimated for successful decoding at the receiver. This paper addresses the design of optimal training sequences for efficient estimation of MTOs and multiple channel parameters. A new hybrid Cramer-Rao lower bound (HCRB) for joint estimation of MTOs and channels is derived. Subsequently, by minimizing the derived HCRB as a function of training sequences, three training sequence design guidelines are derived and according to these guidelines, two training sequences are proposed. In order to show that the proposed design guidelines also improve estimation accuracy, the conditional Cramer-Rao lower bound (ECRB), which is a tighter lower bound on the estimation accuracy compared to the HCRB, is also derived. Numerical results show that the proposed training sequence design guidelines not only lower the HCRB, but they also lower the ECRB and the mean-square error of the proposed maximum a posteriori estimator. Moreover, extensive simulations demonstrate that application of the proposed training sequences significantly lowers the bit-error rate performance of multi-relay cooperative networks when compared to training sequences that violate these design guidelines.