Nokia ones included are awful. They sound tinney and hollow with little or no bass.
They should do what SEs do and have the first part of the headphones with the switch pluggable so you can dump the useless ones then send with the phone for your own decent ones.

Personally I recommend creative headphones.

Seinnhieser (SP) are too expensive and I don't think they perform well at all. Bose are like iPhones, a fashion/lifestyle brand for those who know no better. And equally as expensive!

Skullcandys are also decent headphones.