Size is utterly irrelevant to me, unless it's bigger than the Wuhrlitzer jukebox at the drive in. My main criterion is S/Q first, price second, & ergonomics third (unless it's a real pig, ergonomically).
I'll confess I don't know what AAC is...if it's lossless I'd try it, but I'm pretty much done with perceptual encoding. At the best VBR bitrates none I've used are transparent enough with acoustic music (although MP3 @ 320 VBR is okay for 90% of the rock I've tried it with).
J&R has the 40 GB Nomad for $249.95, so looks like the mark to beat if the Zen is "all that & a bag of chips."