We employ Ca II K and Na I D interstellar absorption-line spectroscopy of early-type stars in the Large and Small Magellanic Clouds (LMC, SMC) to investigate the large- and small-scale structure in foreground intermediate- and high-velocity clouds (I/HVCs). Data include FLAMES-GIRAFFE Ca II K observations of 403 stars in four open clusters, plus FEROS or UVES spectra of 156 stars in the LMC and SMC. The FLAMES observations are amongst the most extensive probes to date of Ca II structures on ∼20 arcsec scales in Magellanic I/HVCs. From the FLAMES data within a 0 ∘.∘.∘.5 field of view, the Ca II K equivalent width in the I/HVC components towards three clusters varies by factors of ≥10. There are no detections of molecular gas in absorption at intermediate or high velocities, although molecular absorption is present at LMC and Galactic velocities towards some sightlines. The FEROS/UVES data show Ca II K I/HVC absorption in ∼60 per cent of sightlines. The range in the Ca II/Na I ratio in I/HVCs is from –0.45 to +1.5 dex, similar to previous measurements for I/HVCs. In 10 sightlines we find Ca II/O I ratios in I/HVC gas ranging from 0.2 to 1.5 dex below the solar value, indicating either dust or ionization effects. In nine sightlines I/HVC gas is detected in both H I and Ca II at similar velocities, implying that the two elements form part of the same structure.