Shortest Identifying Substring
Pyth, 22 21 bytes

hfqzho&gt;xNT0Sf}TY.z.:z


isaacg and me got the same 21 solution more or less at the same time. So he deleted his solution. 

Try it online: Pyth Compiler/Executor

Explanation

                         implicit:  z = first input line
                                   .z = all other input lines
 f                .:z   filter all substrings T of z, which satisfy:
            f   .z        filter .z for lines Y, which satisfy:
             }TY            T in Y   
           S              sort these lines alphabetically
     o                    order these lines N by:
      &gt;xNT0                 (index of T in N) &gt; 0
                          (sorting in Pyth is stable, so this brings the lines,                      
                           which start with T, to the beginning
                           without messing up the alphabetically order)
  qzh                     z == first element of ...
h                       print first elment