It has to be the most linux friendly, have the highest compression rate and [b]security[/b].
What exactly do you refer to when you mention security
? Do you want to password encrypt these archives, or are you looking for a format that is somewhat more resistant to corruption?
I know that the format rar is can add a defined amount of redundancy to an archive, thus making the archive more robust when it comes to corruption; the catch is that the rar format isn't open. I don't think that GNU tar has the same feature built in, but third party utilities might provide something similar.
When it comes to efficiency, all tests I have seen so far indicate that the compression ratio of bz2 is superior to that of it's older counterpart gz, but that efficiency boost comes at the price of requiring more CPU time. I don't have anything to contribute regarding other formats (xz, 7z, etc); see Matthews excellent answer for some raw numbers on this issue.