The principal theme of this thesis is the interplay between symmetry and regularity in discrete structures. The most general class of structures we consider are coherent configurations, certain highly regular colorings of complete graphs. This class includes such diverse structures as the orbital configurations of permutation groups and association schemes originating from the design of experiments in statistics. Metric schemes, a subclass of association schemes, are derived from distance-regular graphs. Johnson, Hamming, and Grassman schemes are special classes of great importance among metric schemes. We study structural and spectral properties of coherent configurations. As a culmination of this analysis, we confirm Babai's conjecture on the minimal degree of the automorphism group for distance-regular graphs of bounded diameter and primitive coherent configurations of rank 4. The minimal degree of a permutation group $G$ is the minimum number of points not fixed by non-identity elements of $G$. Lower bounds on the minimal degree have strong structural consequences on $G$. Babai conjectured that for some constant $c>0$ the automorphism group of a primitive coherent configuration on $n$ vertices has minimal degree $\ge cn$ with known exceptions. If confirmed, this conjecture gives a CFSG-free proof of the Liebeck-Saxl classification of primitive groups with sublinear minimal degree. In this thesis, we confirm Babai's conjecture for distance-regular graphs (metric schemes) of bounded diameter and primitive coherent configurations of rank 4. Central to our approach is the study of spectral parameters of distance-regular graphs, such as spectral gap and smallest eigenvalue. The spectral gap of a graph is known to be tightly related to expansion properties of the graph. Hence, lower bounds on the spectral gap are widely applicable in various areas of mathematics and theoretical computer science. We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. At the same time, graphs of which the smallest eigenvalue has a small absolute value are known to enjoy a rich geometric structure. We characterize Hamming graphs as distance-regular graphs of diameter $d$ with smallest eigenvalue $-d$ and $\mu\leq3$, under mild additional assumptions. We also characterize Johnson and Hamming graphs as geometric distance-regular graphs satisfying certain inequality constraints on the spectral gap and the smallest eigenvalue. Finally, we study robustness properties of certain classes of coherent configurations. For instance, we show that the family of Johnson schemes is robust in the following sense. If a homogeneous coherent configuration $\xxx$ on $n$ vertices or its fission contains a Johnson scheme $J(s, d)$ as a subconfiguration on at least $5n/6$ vertices and $s>250d^4$, then $\xxx$ is a Johnson scheme. This result strengthens a 1972 Kaluzhnin-Klin theorem that corresponds to the case where the subconfiguration itself has $n$ vertices. Our result is also related to Babai's ``Split-or-Johnson lemma'' and in particular to the philosophy in the theory of Graph Isomorphism testing that we can either find structure or find efficiently verifiable asymmetry. We show that similar robustness results hold for Hamming and Grassmann schemes.