Animals chain movements into long-lived motor strategies, exhibiting variability across scales that reflects the interplay between internal states and environmental cues. Understanding how these complex patterns in behavior emerge requires a comprehensive approach that embraces variability across scales. We build high-fidelity Markov models from maximally-predictive sequences, bridging across scales from posture dynamics to long-lived navigation states across species. In C. elegans and larval zebrafish we find that behavioral plasticity leads to heavy-tailed statistics in behavior. Additionally, we introduce new approaches for measuring phenotypic variation across behavioral timescales, and find structure to inter-fish variability that reveals how sensory inputs and motivational states drive behavioral variation along an exploration-exploitation axis.