Get the Creative Vision: M. It is exactly like the Video IPod, except not made by Apple, of course (Made by Creative Labs). The thing is awesome - Never had a single problem with it.
You don't need a program like ITunes, all you need is Windows Media Player. It will convert your video files if needed.
Also, read some C-Net reviews on it- it was rated top Media Player, over all Ipod models.