In the problem of fast bipedal locomotion on uneven terrain, one of the key challenges is in establishing stable footholds. We present an approach for analytically computing the optimal impedances for completing a safe and stable foothold. The robot foot-leg behavior is modeled as a free-floating two-link system making contact with an uneven surface. The optimal impedance is derived directly from minimizing a cost function based on the Center of Pressure (CoP) at the instant of making full ground contact. The obtained impedance is shown to be linearly dependent on the orientation of the ground, for a given desired terminal state and CoP position. Consequently the impedance can be estimated based on an expectation of ground orientation at the point of foot contact. The proposed approach is validated in a walking simulation on the full iCub humanoid robot.