If you're looking for something other than an iPod (lets face it, almost everyone has one, so they're not cool... and Borat is right, iPod Minis are for girls
) then you may want to check out the Zen Vision M.
It has the added benefit that it can play back movies in XViD and other common formats without a recode, (Which is why I use it as a PMD instead of my PSP) and also that it doesn't use iTunes (which I despise since it tries to convert all my WMA files to MP3 AAC).
I've not had a chance to look at the Zune yet, but I doubt it'll be anything special.