...For anyone considering a Nano (not me for aforementioned storage reasons, but I know this meets some people's needs), Sandisk has kicked out a new Sansa model.
I really like the Sansas as dedicated PMPs; they do just about everything right. (The company even officially supports 3rd-party efforts like Rockbox).
Product Page
It's got 16GB flash memory, an FM radio and a voice recorder function, your typical array of supported codecs, and a microSDHC slot (supports microSD/SDHC up to 24GB). Supposedly 24 hours of audio playback or 7 hours of video playback to a charge.
Not bad for $200, I suppose.
So, if you're considering the Nano, there's an alternative.
If you're torn between the Classic and the Touch, the Archos 605 (which I mentioned earlier) has all the best from both of those devices, though the Archos UI feels a little PocketPC-ish.
There are a couple of things to mull over.