This paper considers the Unit-modulus Least Squares (ULS) problem, which is commonly seen in signal processing applications, e.g., phase-only beamforming, phase retrieval and radar code design. ULS formulations are easily reformulated as Unit-modulus Quadratic Programs (UQPs), to which Semi-Definite Relaxation (SDR) can be applied, and is often the state-of-the-art approach. SDR has the drawback of squaring the number of variables, which lifts the problem to much higher dimension and renders SDR ill-suited for large-scale ULS/UQP. In this work, we propose first-order algorithms that meet or exceed SDR performance in terms of (approximately) solving ULS problems, and also exhibit much more favorable runtime performance relative to SDR.We specialize to phase-only beamformer design, which entails additional degrees of freedom that we point out and exploit in two custom algorithms that build upon the general first-order algorithm for ULS/UQP. Simulations are used to showcase the effectiveness of the proposed algorithms.