nano: stores only 8GB, doesn't do video. but it's a very small and more pocketable. you may have to split your library up to get stuff on there (for example, mine is approaching 20GB which couldn't fit into 8GB). metal case so less likely to scratch and generally tougher.
video iPod: stores a lot more, does video, but is larger than the nano (though still not exactly big). can likely store your entirely library all at once. plastic case: scratches easily.
Do you happen to know anything about the length of their lives? My 4th gen iPod just died after 2 yrs and minimal usage. I had heard that the nanos are built to last longer, but my source was not so reliable. Any thoughts on that?
I've got a Nano 4Gb and a Video Ipod 30G. Unless you want the video's go for the Nano the battery lasts twice the time and for some reason the sound is better and you can wear it on your arm with a wristband.