I had kinda the same choice, was going to get a shuffle over another MP3 player. Now, unless you need iTunes or something, consider another choice for MP3 player.
Well honestly ...imo the Samsung YP-u2 is a WAAAY better choice then a Shuffle. The sound that comes out of the Samsung is MILES ahead of a shuffle. Its kinda the same setup to. There is no cord , it plugs right into a USB port, just like the shuffle. When you first buy the Samsung its a MTP device, meaning you need WMP to transfer. However, after extensive research i found that you can flash the samsung to a euro firmware and it becomes a UMS device (Universal Mass Storage device, just like a flash drive). It has a display which is clear and easy to read. It has a 9 band eq (YES 9 band) and has 10 or so presets including 5 3d presets. Now if you havent heard the 3d presets you are REALLY missing out. 1 of those settings alone DESTROY the sound on a shuffle.
I have to tell you that the Samsung is a AWESOME player...ive been using it in my car while plugged into my car stereo. Its FANTASTIC sound. The supplied earbuds are alittle muddy...but get the job done. I quickly replaced them with a pair of Koss KSC-75's and its a NIGHT AND DAY difference. BTW, if you need headphones, i HIGHLY suggest these KSC-75's. I picked them up from Radio shack for 19.99, INSANE deal on a great sounding headphone. Probaly the best sound for you buck.
With Mp3 players now using 3d sound, or SRS, EAX, its very hard to find a phone with that type sound quality. Phones are great for those off moments when you need alittle get away, but for MP3's to sound really good, its better to get a player. They are far ahead of phones in terms of sound quality. However, i know phones are very far behind...meaning in a year or so, phones will probaly adopt 3d sound of some sort, if some havent already.