Probably best to just forget about the old P1 and P2 plans.
My understanding as best as I can briefly explain it:
Power Apps connectors are classed as standard or premium. You can use standard connectors with O365 licenses for no additional fee. Premium connectors require a premium (per user or per app) license which is extra (even if you have higher level licenses like E5).
You can buy an expensive ($40 per user per month) 'per user' plan, which allows a licensed user to use as many Power Apps with premium connectors as you like.
You can buy a cheaper ($10 per user/app) 'per app' plan that allows a licensed user to access two specific Apps (which should be related to the same business function, though whether/how this is enforced I have no idea, technically I expect you can just use any two apps).
To build anything really robust, you'll need a premium connectors (otherwise you'll have to use SharePoint as a datasource which comes with all manner of limitations, issues and risks). All the really useful connectors like http are premium and even connectors to many other MS services (which you have to pay for separately) are premium, such as SQL Server and Azure Blob Storage. Some of the standard connectors (such as many of the cognitive services ones) don't expose all the parameters they should, so you may end up having to resort to http (premium) even to use these services for which connectors exist.
For larger customers there are discounts/sales on the licenses, so you may want to look into that, though if I were in charge of budgeting I wouldn't want to make long term commitments on the basis of discounts.
There is a preview 'Power Apps for Teams' version which allows you to use a limited version of Dataverse without a premium license. However this is
A) Preview (so, known bugs and flakey),
B) Only works inside Teams which may not work for your scenario,
C) Has various limitations (such as some features/controls are incompatible),
D) Is an even more limited version of Dataverse (which is already incapable of querying more than one join deep which makes it a poor choice for the sort of relational data scenarios I personally work with),
E) Not guaranteed to remain a free option.
OK, so that wasn't so brief and turned out a bit cynical, but hopefully of some use...
