Material challenges are the key issue in Majorana nanowires where surface disorder constrains device performance. Here, we tackle this challenge by embedding PbTe nanowires within a latticematched crystal, an oxide-free environment. The wire edges are shaped by self-organized growth instead of lithography, resulting in nearly-atomic-flat facets along both cross-sectional and longitudinal directions. Quantized conductance plateaus are observed at zero magnetic field with channel lengths reaching 1.54 $\mu$m, significantly surpassing the state-of-the-art of III-V nanowires (nearly an order-of-magnitude improvement compared to InSb). Coupling PbTe to a Pb film unveils a flat interface spanning microns and a large superconducting gap of 1 meV. Our results meet the stringent low-disorder requirement for the definitive observation of Majoranas.