Fluorescence lifetime imaging (FLIM) is used for measuring material properties in a wide range of applications, including biology, medical imaging, chemistry, and material science. In frequency-domain FLIM (FD-FLIM), the object of interest is illuminated with a temporally modulated light source. The fluorescence lifetime is measured by computing the correlations of the emitted light with a demodulation function at the sensor. The signal-to-noise ratio (SNR) and the acquisition time of a FD-FLIM system is determined by the coding scheme (modulation and demodulation functions). In this article, we develop theory and algorithms for designing high-performance FD-FLIM coding schemes that can achieve high SNR and short acquisition time, given a fixed source power budget. Based on a geometric analysis of the image formation and noise model, we propose a novel surrogate objective for the performance of a given coding scheme. The surrogate objective is extremely fast to compute, and can be used to efficiently explore the entire space of coding schemes. Based on this objective, we design novel, high-performance coding schemes that achieve up to an order of magnitude shorter acquisition time as compared to existing approaches. We demonstrate the performance advantage of the proposed schemes in a variety of imaging conditions, using a modular hardware prototype that can implement various coding schemes.