On a Crystalline Variational Problem, Part I: First Variation and Global L-infinity Regularity