Structure-From-Motion (SFM) methods, using stereo data, are among the best performing algorithms for motion estimation from video imagery, or visual odometry. Critical to the success of SFM methods is the quality of the initial pose estimation algorithm from feature correspondences. In this work, we evaluate the performance of pose estimation algorithms commonly used in SFM visual odometry. We consider two classes of techniques to develop the initial pose estimate: Absolute Orientation (AO) methods, and Perspective-n-Point (PnP) methods. To date, there has not been a comparative study of their performance on robot visual odometry tasks. We undertake such a study to measure the accuracy, repeatability, and robustness of these techniques for vehicles moving in indoor environments and in outdoor suburban roadways. Our results show that PnP methods outperform AO methods, with P3P being the best performing algorithm. This is particularly true when stereo triangulation uncertainty is high due to a wide Field of View lens and small stereo-rig baseline.