Ipods have arguably the best user interface of all the mp3 players. It's simple and intuitive for just about anyone. You will generally have to pay a premium for an Ipod over, say, a Sansa player of the same size. Also, the songs that you download from the Apple store are in a proprietary format that will only play on Ipods. So if you switch to another brand down the line, you're screwed. Ipods do play mp3 files as well, so I just keep all my files in that format and don't buy from Apple.
The first decision is whether you want a tiny player of around 2-8 GB or do you want one with a massive hard drive that will hold your entire music collection. In general, 1GB of memory will hold around 10 CD's. Thats just an approximation, and it varies depending on the amount of compression used to make the mp3 file. If you're just planning to store music on the player and not video, I would go for the small size with flash based memory (in other words, no hard drive, no moving parts). 4 GB would hold at least 40 CD's, probably more.