I just got my wife a Nano, but it was largely because she already used iTunes to handle her music and, IMO, having good front-end software is huge for something like this.
iRiver and Sandisk are the big ones to look at next to the Nano. If you have the chance, try out each of their interfaces and see what you like.
What turned me off from the iRiver and Sandisk was that you have to use Windows Media Player to manage your music. It's a very similar approach to iTunes, but I don't like it as much - your opinion may vary.
I think the iRiver and the Sandisk are a wash with the Nano on format support. None of them support FLAC. The iRiver and Sandisk support WMA, but not AAC and the Nano is the opposite. The iRiver does add ogg, but unless you rip to that, you won't encounter it much "in the wild". If you have an online music store preference, that will probably push you one way or another.
Battery life is supposed to be excellent on all of them - they just improved it more on the Nano (don't discount HD players on this item - they have excellent battery life these days). I haven't seen a comparison of audio quality between them, nor would I really trust one unless it was from a reputable audio person (and not a tech person).
The Sandisk does have a memory card slot for some expansion, which it nice. The Nano has the most options for accessories and integration with things like car stereos.