You could make a graphical web installer like Mozilla uses. All the components not yet on the users' system can be detected and installed (including CPAN.pm).
This is a lot of work, especially if done from the ground up, but i encourage people to do it because it will make installing SO MUCH easier. Windows users will expect nothing less.
If only someone would make a cross-platform graphical installer generator.