Ok so I've gone the route of including all non-CORE and non-XS dependencies bundled in an extlib in my distribution to make things as easy as possible for people trying to install the software, looks to be a good way.
When I started building the extlib in my development environment using cpanm -L extlib <module> etc I realized that cpanm installs everything in a local::lib compatible way, meaning everything doesn't go starting at extlib but rather extlib/lib/perl5. Therefore I would have to use local::lib "$FindBin::Bin/../extlib" in my programs instead of use lib "$FindBin::Bin/../extlib" to get use the dependencies in extlib but this brings a chicken-or-egg problem, local::lib in not in CORE :-(
Is there something I'm not thinking right here? I don't want to make to have to make an external dependency that people have local::lib already installed in their Perl tree (which could require administrator access)