While implementing my module File::Modified (nee File::Dependencies - not yet on CPAN), I also wanted such a deep comparision method, but I didn't find one either (in Python, this would be as easy as struct_a == struct_b :-)). But I would prefer basing the thing on Data::Dumper or another existing wheel, as cyclic structures are a nasty thing to handle. On the problem of hash order, it would make sense to do a sort() on the keys of the hashes before writing them out, so that identical hashes produce identical strings - maybe that would be just a small patch to Data::Dumper.
Update : Of course, somebody already invented this wheel, in Test::More by Michael Schwern. There is the routine is_deeply, which does a deep compare - maybe this would warrant extraction in its own module...
perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ; # The
$d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider
($c = $d->accept())->get_request(); $c->send_response( new #in the
HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' # web