Depending on the budget you can go for a IPod or Creative Zen Ultra. These two are probably the best "large" MP3 players with capacity at 15GB+. MIPo also offers a "large" capacity drive and maybe worth looking into.
For a kid as a gift the MP3 stick idea is a good one. But I would simply ask the child what he/she wanted. I'll explain shortly.
I think iPod and Zen are good ones too if you are looking to spend that kind of money. Having said that, I think we should add the iRiver IHP 120 as it is better IMHO. Why? Because I just bought one, it isn't here yet though.
When looking for an MP3 player to listen to whilste riding my bike, I was like the other poster in that I knew very little. I was quickly overwhelmed with the hype, predjudice and choices. It occured to me that the process was much like designing a personal computer for yourself to build and one has to define need and then balance with cost. So I set down and made a list of what was important to me. That's why you need to ask the kid what they want, that list will differ from mine.
Quality, I don't like cheap and I don't like things that break. Sorry iPod your out.
Versatility, I wanted to be able to play several formats including Ogg. Did I mention iPod yet?
Size, it had to be lightweight.
Capacity, it needed to hold a lot of stuff
Speed, You gotta have USB 2.0 when you transfer a lot of files
Rechargable batteries with long life- I hate buying batteries
FM radio - why not?
The iRiver filled the bill and then some with optical I/O for playing on larger systems, wired remote with backlit display, it can handle many file types, even jpeg or avi or txt for transfer of work from one box to another, built in mike for voice recording, it also has the ability to encode music 40-320 kbps without a PC, updateable firmware - etc. One thing it can't do is record direct from FM radio- but who does that? FM is no longer much different than AM with DJs yakking endlessly and cutting off tunes. Another downside, it was very expensive -over 300 bucks US. However, it has a 20 gig hard drive that shows up as external memory on XP, no installation files needed. Drool. I just hope I can work the damn thing when I get it this afternoon.
Plus, I read the earbusds suck so I bought some Sony Fontopias for an additional 33 dollars.
Just my 2 cents worth.