A big part of my job is testing headphones and headsets related to all the handsets and such you could think of and my recommendation is as follows:
Iphone has best SQ by far - with OS 3.0 it will also get, amongst the many cool things, wireless audio support via bluetooth A2DP which is really the next thing acording to the devices I've seen, heard or been part in development of. And yes the new Iphone might be even better. But still they are over most budgets even if they have the best analog output and possiblity of some digital outputs.
Music Nokias are in generel not bad but a few have some weird stuff going on like compressions etc. you can't turn off. Havn't got the chance to look at the 5800 yet but I doubt it would be a bad buy according to my intel. I personally have a N73 which is a living nightmare UI vise but SQ is okay.
SE music handsets are some of best and I know several people who swears to them unless you go Iphone. But again some of them have kinks - especially becouse they are not like HTC or Nokias based on a few well developed platforms but rather a lot of smaller sub divisions which leads to alot of mishaps UI wise etc.
HTC's high end are not bad but not special ether when it comes to SQ - the SE Xperia is good for an handset SQ wise but brick heavy and not near Iphone smart.
All in all as a Head-Fi member and sworn crApple sceptic even I am thinking of saveing for an Iphone - maybe the new one just for the SQ which doesn't come better unless you go dedicated media player device.
However I'd like to state that there is one other thing going on - the current trend towards very well sounding lossy bluetooth stereo headsets which have build in amplification and better DAC than a handset can afford. Also since the spec's is out around the new Iphone convention in a year or 2 we will see Lossless wireless stereo headphones via bluetooth 3.0 that has way better SQ than anything analong we see now even with a cheap handset as long as it doesn't tingle with the bits its sending to the headphone. Lossless, wireless, internel tuned to product amping and HQ DAC just can't be beat. Well okay I have a stake in the latter as I'll properly be heavily involved in selling and developing that
Cheers and hope it helps someone