During the zombie nights of the worst-ever jetlag I spent some time reviving my 4G iPod. Just before its release 3.0 was announced on Slashdot, I installed Rockbox on my ipod. It's fantastic! The installation was smooth (unzipping a file and running an executable that will tweak the bootloader). With it you can do more things with the playing song than what you could do with the Apple stock interface. You can save locations in a song as bookmarks, change the pitch, and there are more things in the context menu that I haven't tried. The fade-in/fade-out on play/pause is pleasant. Also there are cross-fade options.
You can program it to pause the song when you remove the headphone jack. You can organize the songs in more sane format
Do try it if your device is on the supported list!
As for the other discovery - Nerina Pallot.
Some awesome tracks: Geek Love, Damascus, Everybody's gone to war, Sophia