I've got two programs that are reliant on GNU based applications which Perl does "system" calls as part of the script. Obviously this creates a dependency on something external to Perl, which I'm not overly keen on.

You're absolutely right not to be keen on scripts that execute commands via system. Here lies non-portability.

What you need to do is to look and see if the equivalent of the command exists in perl - either in the core distribution, or available from CPAN.

As others have pointed out, the equivalent of find is available inside perl, see File::Find.

If you can list out what commands are being run externally, we might be able to suggest appropriate modules for you.