Is there a reference dereference happening?

Yes - the curlies directly around the map create a hash reference from the list that map returns (see number 3 in Making References), and then the outer %{ } dereferences that hash reference (see number 2 in Using References).

So the inner pair is a code block.

Nope, it's a hashref constructor, but since it can also look like a block, Perl sometimes has to "guess" which one it is, and AFAIK that's where the warning is coming from.

If I need to return an array, as opposed to a list or a hash, what would that syntax be?

The same kind of reference-dereference operation, just in this case create an arrayref with [...] and dereference it with @{...}:

print Dumper @{ [ map {"<$_>"} qw/a b c/ ] };
__END__
$VAR1 = '<a>';
$VAR2 = '<b>';
$VAR3 = '<c>';
[download]

Although I think this is needed less often than the %{{...}} trick when it comes to passing stuff to functions, since most functions impose list context on their arguments anyway. However, it is sometimes used as a trick to interpolate things into strings that don't normally interpolate, so for example:

sub foo { return "World!" }
print "Hello, ", foo(), "\n";   # prints "Hello, World!"
print "Hello, foo()!\n";        # prints "Hello, foo()!"
print "Hello, @{[ foo() ]}\n";  # prints "Hello, World!"
[download]

While in this example the first print looks cleaner than the last, the trick can sometimes be useful when interpolating things into long heredocs, for example.