I just picked up some Sony MDR-EX51LP headphones [^].  I highly recommend them - nice and small, fit snugly in your ear, and they pack a lot of low end even though they're tiny.  They come with a variety of earbuds of different sizes to try out, plus a neat little carrying case.  I haven't had a nice compact pair of headphones like these in years.