We present new exponential bounds for the Gaussian Q function (one- and two-dimensional) and its inverse, and for M-ary phase-shift-keying (MPSK), M-ary differential phase-shift-keying (MDPSK) error probabilities over additive white Gaussian noise channels. More precisely, the new bounds are in the form of the sum of exponential functions that, in the limit, approach the exact value. Then, a quite accurate and simple approximate expression given by the sum of two exponential functions is reported. The results are applied to the general problem of evaluating the average error probability in fading channels. Some examples of applications are also presented for the computation of the pairwise error probability of space-time codes and the average error probability of MPSK and MDPSK in fading channels.