I don't think that requiring installation of a particular package when an adequate alternative is already installed is a satisfying solution. I haven't attempted to code such a requirement into Makefile.PL (or cpanfile) and see how the various CPAN clients handle it. I should probably do so.
The run-time code would still need to select amongst the installed packages, so the original question woould still be cogent.
I wonder if some sort of capabilities database would be of help here. Modules providing capabilities would be registered upon installation. At run time the database would be queried to determine which modules were available; if one hadn't been loaded, one would be.