Unmanned Aerial Vehicles (UAVs) are emerging as important users of next-generation cellular networks. By operating in the sky, UAV users experience very different radio conditions than terrestrial users, due to factors such as strong Line-of-Sight (LoS) channels (and interference) and Base Station (BS) antenna misalignment. As a consequence, the UAVs may experience significant degradation to their received quality of service, particularly when they are moving and are subject to frequent handovers. The solution is to allow the UAV to be aware of its surrounding environment, and intelligently connect into the cellular network taking advantage of this awareness. In this paper we present REgression and deep Q-learning for Intelligent UAV cellular user to Base station Association (REQIBA), a solution that allows a UAV flying over an urban area to intelligently connect to underlying BSs, using information about the received signal powers, the BS locations, and the surrounding building topology. We demonstrate how REQIBA can as much as double the total UAV throughput, when compared to heuristic association schemes similar to those commonly used by terrestrial users. We also evaluate how environmental factors such as UAV height, building density, and throughput loss due to handovers impact the performance of our solution.