Matt got me a 5th gen video iPod (30 gig), and I love that, even though I don't actually use the video. I just love it for the space. But I also listen to a lot more music than the average person, and my iTunes is basically bursting with almost 8000 songs (and counting!). So it kind of depends on how much music he listens to. Will he actually use the space to bother spending the money for a bigger iPod? Or will he be fine with a few hundred songs?
Nanos are kind of more customizable, as they do come in several colours, so they're fun that way if that's how you wanna go.