Quick bit of capacity math:

Assuming very low quality 96kbps MP3 files:
128 megabytes of storage will get you just over 3 hours of non-repeat playback.
64 megabytes of storage will get you 1.5 hours of non-repeat playback.
32 megabytes of storage will get you 46 minutes of non-repeat playback.

Assuming barely-tolerable 128kbps MP3 files:
128 megabytes of storage will get you just over 2 hours of non-repeat playback.
64 megabytes of storage will get you 69 minutes of non-repeat playback.
32 megabytes of storage will get you 34 minutes of non-repeat playback.

Assuming decent quality 160kbps MP3 files:
128 megabytes of storage will get you 1.86 hours of non-repeat playback.
64 megabytes of storage will get you 55 minutes of non-repeat playback.
32 megabytes of storage will get you 27 minutes of non-repeat playback.