The smaller ipods are overpriced, you do pay a lot for the name. But you're also paying for the access to millions of accessories.
If I were buying now, I'd buy the 80GB ipod video. Dollars per gig, it's the best deal, and lots of the features of the Zen or Zune I would never use (fm radio? 3-use wireless sharing? please.)
It sounds like you're more interested in physical size rather than storage capacity, so our foci might not be the same, but depending on your usage patterns, I'd definitely suggest looking at the HD based ones.