Very very few devices support MP4 and H.264. As far as I know, iPod is the only one. Some of the other video players use Flash, which is fairly high quality, but not widely used, and the Zune uses Windows Media formats which is much lower quality and also not widely used.

Yes, you want an MP4 player. MP4s have been the audio gold star standard for a very long time now, and recently the video format has become such as well. All MP4 players also can play MP3s, but it's not the other way around.

Why don't you want iTunes? There are ways to use an iPod without iTunes, it's not as user friendly, but I know that it can be done.

Out of curiosity, where do WMP users buy music/videos from? M$ doesn't have it's own store do they?