What is it about crypto modules that makes them almost universally badly packaged?
Fair enough, crypto can be complicated, but is there some inherent property of that area of programming that makes them so much of a mess?
Many of the classic packaging anti-patterns are displayed in the various depths of the dependency chains of modules like OpenPGP or Net::SSH::Perl, both of which are more or less impossible to install.
For Windows people, this is huge. The crypto modules are littered with unix assumptions and close-minded authors. In at least one case, when the Strawberry Perl compatibility team tried to contact the author to help him add support for Win32, they were told that "You people go back to your stupid Winblows. There's no way I'm adding support for it".
With the gpg command line generally not available on Windows, and the Perl OpenGPG module unable to install because of people like the above, this completely torpedoed any chance of having CPAN clients do security checks by default, or check signed modules.
Having "options" in your Makefile.PL is almost universally bad.
Now, sometimes Makefile.PL script cannot auto-configure and need to ask for things like library paths, or your ORACLEHOME path or what have you. This is just fine, since it's a last resort.
But have a look at some of the questions for Net::SSH::Perl.
As of version 1.00, Net::SSH::Perl supports both the SSH1 and
SSH2 protocols natively. The two protocols have different
module prerequisitives, so you need to decide which protocol(s)
you plan to use. If you use one or the other, only those modules
for your chosen protocol will be installed; if you choose both,
all of the supporting modules will be installed. Please choose
the protocols you'd like to use from the following list ("Both"
is the default).
 Both SSH1 and SSH2
Which protocol(s) do you plan to use? 
Some of the Net::SSH::Perl ciphers depend on a Crypt:: module from
CPAN. You may already have the necessary modules installed, in which
case you don't need to bother with this step. Otherwise you'll need
to install at least one cipher to use Net::SSH::Perl. Please choose
at least one from the following list (Crypt::IDEA is the default).
Enter your choices, separated by spaces: 
Checking for optional modules
Crypt::RSA is required if you wish to use the ssh-rsa public
key algorithm (ssh-dss is used by default).
Would you like to install it? (y/n) [y]
These sorts of questions assume that the person installing the module understands the same things the author does. That is, they understand crypto well enough to answer questions.
I personally argue that people should be able to install CPAN modules without knowing Perl at all.
One common response to that is that CPAN should be for Perl developers, not Perl users that don't know Perl. But what is a Perl developer? What separates a one week old newbie programmer from someone that doesn't know Perl at all? Very little.
And in particular, in module installation the recursion problem dictates that the Perl you are asking questions is probably just trying to install Plagger or Jifty or something else that is several layers abstracted from your module, and has no idea whatsoever about that specific domain.
For example, there's another question missing from that set of questions regarding something called "bubble babble" which I only know of as a video game.
Worst of all, many of these options commit you to one working one particular way in the future forever. The only way to change that decision is to reinstall the module.
In particular, if you are using binary packages from some distribution, you can't do that anyway. If your binary package of Template Toolkit comes without the optional "Splash!" stuff, then too bad
One nice way to sloganeer this problem is as follows.
"For every option that you put in your Makefile.PL, RedHat will answer it wrong"
(this refers to the long history RedHat has of doing weird things with Perl and related packages).
What can you do about this?
There's a couple of fairly straight forward things that can be done to achieve what you want in any case.
Firstly, if the dependencies are themselves relatively sane (they work on all platforms and you don't mind inheriting any baggage they may have) they just make them a full dependency.
This adds some module bloat, but if those modules WORK, then it's not a problem.
Secondly, don't make it an option at all, just don't depend on the module.
If something one layer above needs it, then THEY can add the dependency on the optional module.
Thirdly, can that optional functionality be separated into a different distribution? Then do that instead.
The highly structured way of splitting this out is to make use of driver or plugin APIs.
And above all, remember this.
There are probably hundreds of thousands or millions of Perl programmers in the world. There are only 5000 on the CPAN. So merely by virtue of having uploaded someone to CPAN you are quite probably already in the top percentile or better.
So try to ALWAYS apply a low estimate for the experience of your users, and try to "Just make it fucking easy to install".