Solver-o-matic
Decision Tree for Nonsmooth Optimization Software
Your first choice should be Limited Memory Bundle Method (LMBM) by N. Karmitsa. LMBM is specifically developed for large-scale nonsmooth optimization but, naturally, it can be used also for smaller problems. It works best for highly nonlinear functions. The Fortran 77 source code and the mex-driver (for MatLab users) are available.
For other choices, see e.g.