We report Far-Ultraviolet Spectroscopic Explorer ( FUSE) observations of interstellar O vi absorption in the halo of the Milky Way toward 12 early-type stars in the Large Magellanic Cloud ( LMC) and 11 in the Small Magellanic Cloud (SMC). The mean column densities of O vi associated with the Galactic halo toward the LMC and SMC are log (N(O VI)] 14.52(-0.14)(+0.10) and 14.13(-0.20)(+0.14), respectively, where the uncertainties represent the standard deviations of the individual measurements about the means. Significant variations in the O vi column densities are observed over all of the angular scales probed by our observations: 0.degrees5-5.degrees0 toward the LMC and 0.degrees05-3.degrees3 toward the SMC. The maximum factors by which the O vi varies between sight lines toward the LMC and SMC are similar to2.8 and similar to4.2, respectively. Although low-, intermediate-, and high-velocity clouds are present along most of the sight lines toward the LMC, the variations in O vi column densities are found in all of these O vi absorbing structures. The column density variations trace the structure of the hot ionized medium in the Galactic halo on scales of <<80-800 pc toward the LMC and <<6-400 pc toward the SMC ( assuming that the absorption arises within the first 5 kpc above the Galactic plane).