I'm looking for suggestions on how to handle this. Is it better to require modules that are only needed for testing, or to skip the tests with a message to the user?

Three options:

1. Include Struct::Compare in the PREREQ_PM of your modules Makefile.PL.
2. If it's a pure-perl module then package it in with your tests. Stick it in t/lib and add an appropriate use lib line to the test scripts that need it.
3. Skip the tests. If you need to skip a few tests in a test script you can use the method tachyon showed. If you need to skip an entire script it might be easier to use skip_all something like this (untested code):

   BEGIN {
       use Test::More;
       eval 'use Struct::Compare';
       Test::More->builder->skip_all("need Struct::Compare") if $@;
   };
   
   # rest of test script here
   [download]

As to which is better... harder call. My personal tendency would be to do (1) if the tests were about vital functionality, and (3) if it related to things like checking documentation.

For example in Test::Class I require Test::Differences and a few other modules just for testing in the Makefile.PL. However the test I use for documentation are skipped if the relevant modules (Pod::Coverage, Pod::Checker and IO::String) are not available.

Also - you might want to look at Test::Deep if you're testing complicated structures. Might make your job easier.