It all depends on your own tastes. I personally feel that AAC has an
advantage over MP3, which is why it is my digital audio file of choice.
Of course, MP3 is the "safe bet" since it is supported by nearly every
player on the market. AAC will certainly surpass MP3 in the near future
since it's part of the MP4 spec.
I owned an iRiver iHP-120, and it was certainly loaded with features
and had great codec support, but it's interface was clunky. I now own
a 40GB 4G iPod. The interface is superb, but the sound quality is
lacking. Using iTunes to sync with the iPod is a literally
a"hands-off" operation.
My advice is to go to a store like Best Buy or Circuit City and try
each one. Bring your favorite pair of headphones, as well.