I'm also trying to figure out what the best portable media player might be--which for my purposes are slightly different than yours in that I'm more interested in still image storage--but I suggest you also look at the following: Toshiba MES60VK Gigabeat (60 GB) portable media player, Microsoft's Zune, and the Apple 30 GB IPod/Video.
I want to get a PVP, so I've been doing some research and I've narrowed down my choices to the Creative Zen Vision W or the Cowon A2 (but I'm open to suggestions). I'm not all that savvy about file formats or converting them and most of the videos that I've downloaded are AVIs. Do both of these players play them without having to convert them first? What other players will do this? Which do you think I should get?