Depends on how much storage you need. I've used both Classic and Nano iPods and they performed exactly the same. If the Nano meets your storage needs then I would probably get that. But either way you can't really go wrong with either one.
Edit: just saw that your looking at the latest versions for both. If that's the case then I would definitely go with the Nano if it has enough storage for you. Otherwise the Classic is a beast.
I'm partial to the iPod Classic, however, I agree with Beyond Fire in this regard...