I have a Zen Stone Plus, my wife has a second gen Shuffle. I have twice the staorage, don't need special software, can see what song is playing, and it was even cheaper.
Harper i just have to point out i love portals, and the monologue at that section in particular "the companion cube will not try to kill you, if it does you should report this behaviour after the conclusion of the test"....or something like that
I just bought the archos 605 and it was amazing flying across the country and watching 5 episodes of Dexter. If your going to choose go with Zune but if you want to do some more research go with Archos.