Or is one pro license enough? We're running a stage environment and a production environment for the same website. Thoughts?
One is enough you don't need a license for a development server at all source
And here is something from FAQ as well link
Is there a way I can try Craft Client or Pro out before buying?
Yes. As long as you’re running Craft CMS from a non-public-looking domain name (e.g. “mysite.dev” or “staging.mysite.com”), you will have the option to test the Client and Pro editions indefinitely.
And a info from the Terms and Conditions
3. License Agreement Model
This is a single-installation license, meaning you may integrate a Licensed Copy into one public-facing (“Internet”) or internal (“intranet”) web root directory at a time (the “Website”). You may also install and use Craft without limitation for local development and testing purposes.