For those of you who disagree with my opinion on iTunes, thanks for the opposition. A wide variety of viewpoints are a good thing for someone when they're deciding on something, those were just my personal experiences with the software so far. In all honesty, I envy you who have better luck with it!

The fact that I'm running Vista may also have something to do with the compatibility issues, I'm not sure though.
And jones, if these are your primary goals, and you're also concerned with the best "bang for your buck", I say the best audio player on the market period is not made by Apple or Microsoft, but Creative. The Creative Zen Vision M is absolutely the best PMP I've ever had. The software options are broad, the interface on the device is excellent, and though it only comes in 60 gig max, they run a lot cheaper if you can find a deal online. Sound and video quality are also top-notch.
Also, since you're working out with it, do you really want a bulky harddrive-based player with you, especially seeing as they're far more volatile than, say, flash? I work out a few times a week, and even the Touch feels quite big to me when running, it is constantly jostling around in my pocket. There are some nice high-capacity flash players out there, like the
16/32 gig Zen. Don't know if it's anything that would interest you, but options are always nice.
If your ultimate decision is iPod Classic or Zune, though, get a Zune. Apple makes good stuff, but to me, the classic just feels very limited. The ZunePad thingy is a lot nicer than the clickwheel as an interface, and the large screen is also a plus.