Well, that's why suggested to have as many standard libraries as possible into the OS.
Have a meta package for the base installation for the Pyra.
And whenever there's a library that's needed for a new PND that could also be useful for other devs, update the meta-package and the next OS update will include it.
Sure, the dependency lists in the PNDs are a good idea as well and would have a similar result.
Personally, I would prefer a different approach.
1. There is a group of dependencies which are both relatively small and widespread. I'm thinking of zlib, libgl, libssl and the like. These should be included in a metapackage and updated by apt-get. Developers should be discouraged from including these libs in PNDs or statically linking to them, unless a particular app fails to run with up-to-date lib. Libs which are critical to system security (to the point that updating them is practically mandatory) also belong here.
2. Another group of dependencies is widespread but important in size, like java, python, flash, wine (if possible, of course). Also there are packages with distribution policy issues, like codec pack. The user should be able to install these on the system, but do it explicitly. Maybe there could be a possibility to let the user install a certain package on SD (e.g. java) along with PNDs which depend on it. PNDs should include a field telling there is a dependency, so the launcher (both on Pandora and Pyra) could tell what's wrong instead of just failing to run the app. Dependencies themselves could come as .deb packages.
3. Finally, there is a lot of great libraries which could be used by 3-5 PNDs and should be updated from time to time. I believe the best solution is to keep these inside respective PNDs, at a price of having duplicates. Rationale: keep the core system small, stable and predictable. If you include every lib in the core, like ED suggests, there will be (besides obvious bloating) an update every week, and every 5-th update will inevitably break something. Much as you tend to blame the current PND system, it is great because of exactly this approach.