As the application of deep learning continues to grow, so does the amount of data used to make predictions. While traditionally big-data deep learning was constrained by computing performance and off-chip memory bandwidth, a new constraint has emerged: privacy. One solution is homomorphic encryption (HE). Applying HE to the client-cloud model allows cloud services to perform inferences directly on clients' encrypted data. While HE can meet privacy constraints it introduces enormous computational challenges and remains impractically slow on current systems.This paper introduces Cheetah, a set of algorithmic and hardware optimizations for server-side HE DNN inference. Cheetah proposes HE-parameter tuning and operator scheduling optimizations, which together deliver up to 79 \times speedup over the state-of-The-Art. However, HE inference still falls short of real-Time inference speeds by nearly four orders of magnitude. Cheetah further proposes an accelerator architecture to understand the degree of speedup hardware can provide and whether it can bridge HE's real-Time performance gap. We evaluate several DNNs and find that privacy-preserving HE inference for ResNet50 can approach real-Time speeds with a 587mm2 accelerator dissipating 30W in 5nm.