An alternative to jettero's solution is

my %baz;
$baz{$_->[0]}{foo} = $_->[1] for @foo;
$baz{$_->[0]}{bar} = $_->[1] for @bar;

my @baz;
for my $k (sort keys %baz) {
    push @baz, [ $k, @{$baz{$k}}{qw(foo bar)} ];
}
use Data::Dump 'dump';
print dump(\@baz);
[download]

which is very easy to generalize to more than two arrays. The idea is

1. build a hash whose keys are the timestamps,
2. each value is by itself a hash ref,
3. stick the value from each array to some key (like 'foo' or 'bar') of these nested hashes
4. and then build the result array with the key and a hash slice.