We have used FPocket, or MDpocket (which is the same but applied to the results of molecular dynamics). 

the preferable tools depend on what you already know,  and the details you are looking for.

For example concavity searching ( such as what Fernandez-Recio) point out can be very useful, but that is generally all they do --  be careful some (like Fpocket) are intended to account for where a protein or peptide will fit, others such as ligsite are built with small molecule ligands in mind.

    regardless they require a structure, or occasional generate them internally from a sequence

if you have a partner in mind and either structures, or reasonable homology models -- protein protein docking may be of some use.

personally I tend to start with motif searches before I consider the other options (its quick with nice web servers and for a lot of questions it will get you where your going)

--- http://elm.eu.org/ is usually my first (but not only) stop

Thank you for your recommendations!!