I cannot see any other way than to first flatten the structure (like Anonymonk before me) and then to sort and print:

printf "%-15s connected to TCP port %5d %9d times\n", @$_ 
    for sort { $b->[2] <=> $a->[2] } 
    grep { $_->[2] > $max_conns }
    map { my $ip = $_; map { [ $ip, $_, $conn{$ip}{$_} ] } keys %{$con
+n{$ip}} } 
    keys %conn;
[download]

Update: Added the grep-line to incorporate the check as in OP.