Headphones (Grado, Sennheiser, Shure, Audio Technica, AKG, Denon, Bowers and Wilkins), matter as much, if not more than the inherent sound quality of the phone. However, since all music apps will use the phone's sound hardware, I guess you want one with some form of EQ. Winamp Pro, with a 10 band EQ is my choice, on PC as well as Android. Best thing is to download a few and see what you like best.
BTW Sennheiser and Grado are my choices.