Desirable S-box properties What desirable properties should an S-box have?

My current standard selection process is to just pick them at random and verify that they fit the following criteria:


The probability that any random two bits $S[a]_b$ and $S[c]_d$ are equal (for any random $a$, $b$, $c$ and $d$) is 50%.
The probability that any random two bits $S[a]_n$ and $a_n$ are equal (for any random $a$ and $n$) is 50%.
No entries exist such that $S[a] = a$
No entries exist such that $S[a] = \bar{a}$


Are there any other important properties that need to be applied?

Edit My reasons for asking are that I wish to combine this S-Box design with a CBC mode cipher as discussed on this question.
The following information about the DES S-Box might be useful (taken from here):

DES Design Criteria

there were 12 criterion used, resulting in about 1000 possible S-Boxes, of which the implementers chose 8

these criteria are CLASSIFIED SECRET

however, some of them have become known


The following are design criterion:
R1: Each row of an S-box is a permutation of 0 to 15
R2: No S-Box is a linear of affine function of the input
R3: Changing one input bit to an S-box results in changing at least two output bits
R4: S(x) and S(x+001100) must differ in at least 2 bits
The following are said to be caused by design criteria
R5: S(x) [[pi]] S(x+11ef 00) for any choice of e and f
R6: The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input is held constant
R7: The S-boxes chosen require significantly more minterms than a random choice would require

For Rijndael, things were different as the S-Box in Rijndael had to meet certain requirements mathematically and cryptanalytically