- How accurately can one estimate a random parameter subject to unknown deterministic nuisance parameters? The hybrid Cramér-Rao bound (HCRB) provides an answer to this question for a restricted class of estimators. The HCRB is the most popular performance bound on the mean-square-error (MSE) for random parameter estimation problems which involve deterministic parameters. The HCRB is useful when one is interested in both the random and the deterministic parameters and in the coupling between their estimation errors. This bound refers to locally weak-sense unbiased estimators with respect to (w.r.t.) the deterministic parameters. However, if these parameters are nuisance, it is unnecessary to restrict their estimation as unbiased. This paper is the first of a two-part study of Bayesian parameter estimation in the presence of deterministic nuisance parameters. It begins with a study on order relations between existing Cramér-Rao (CR)-type bounds of mean-unbiased Bayesian estimators. Then, a new CR-type bound is developed with no assumption of unbiasedness on the nuisance parameters. Alternatively, Lehmann's concept of unbiasedness is employed rather than conventional mean-unbiasedness. It is imposed on a risk that measures the distance between the estimator and the minimum MSE (MMSE) estimator which assumes perfect knowledge of the nuisance parameters. In the succeeding paper, asymptotic performances of some Bayesian estimators with maximum likelihood based estimates for the nuisance parameters are investigated. The proposed risk-unbiased bound (RUB) is proved to be asymptotically achieved by the MMSE estimator with maximum likelihood estimates for the nuisance parameters, while the existing CR-type bounds are not necessarily achievable.