Weather-API.net says you can get up and running quickly, and claims to have the best pricing, which ranges from free to $199 per month, dependent on request volume.
Weather-API.net uses special caching techniques and database optimization to deliver fast responses despite having so many data points. One key problem it solves is this question: How do you handle multiple stations reporting data near a given location?
"Much of the heavy lifting of the site has to do with this exact question. For any given desired location, there are many nearby reporting stations, but they vary each day and vary in what they provide. For example, a nearby location might not report temperature, or it might report temperature but only 2-3 entries for a given day. So, we have some complex heuristics that analyze what stations are near each location for each and every day of the request and determine the valuable tradeoff between proxity and quality/quanity of data. In the future we may expose options in the query so the user can override these assumptions. For example, if you don't care about temperature but you care about humidity and a station closer to your desired point has humidity but no temperature, we can prioritize distance and humidity of distance and temperature."