Finding a planet with breathable air might be a tad tricky.... oxygen is highly reactive, it readily bonds with other molecules, without something constantly replenishing it, it soon gets bound up in rocks or combined with other gases. Early life on earth was anaerobic, it produced oxygen as a by-product. Without well established life, you're not going to find a convenient, oxygen rich atmosphere.
Terraforming a plant is easy - you just need to find the reactor built by the long extinct aliens. The reactor makes oxygen by melting the turbidium deposits. Start the reactor xes, free Mars...