Here's my opinion on the various types of portable stereos - feel free to add/correct.
1. Portable CD-players - at the moment probably the cheapest and most versatile portable stereo solution, excellent sound reproduction quality (at least with Sony and Panasonic units

, blank CDRs are dirt cheap - around $1/disk, sometimes even cheaper.
Cons: if you want to listen to mp3's, have to convert them to WAV files and then burn to an audio CD, players and media are bulky, only 74 minutes of music per disk. IMHO, skipping is not an issue with the latest players (especially with the new Sony G-protection units).
2. Hybrid CD/CD-ROM mp3 players (play regular CDs as well as mp3's burned onto CD-R. Currently there's only one on the market - the Genica (under several different labels), it's cheap ($100), full of bugs, poor build quality, extremely poor sound quality - in other words, it's total junk. However, things are about to change as the mainstream consumer electronics manufacturers move into the market. Philips has a unit slated for release in late August, which you can check out at
http://www.expanium.philips.com. Last time I heard, Aiwa, Kenwood and RCA were also developing similar units, which isn't surprising, since Kenwood already has a car mp3 CD player on the market, and Aiwa is putting one out this fall. IMHO, this would be the ideal portable stereo for the general consumer. The biggest drawbacks are once again, bulky players and bulky media. Of course one needs to own a CDR drive, but these days everyone and their grandma has one.
3. MD players - they have a lot going for them. Most units have very good sound reproduction quality (powerful bass, etc). The compression algorithm used in today's MD units is roughly equivalent to mp3's encoded at 224kbps (there's a lot of arguments whether ATRAC is inherently superior to mp3, I won't get into that because, frankly, I have no clue

Minidisks are much smaller than CDs and are almost as cheap as CDRs (for example, amazon.com and Circuit City sell 20-packs of 74-minute disks for $30, which comes to $1.5 per disk). Finally, when it comes to looks, MD players look great. When I pay 300 bucks for a portable stereo, it better look like it's worth 300 bucks, and most MD players deliver - the cheapest MD player looks much better than the most expensive MP3 player. As for the cons, the biggest one is the real-time recording (some MD boomboxes and decks offer 2X CD to MD dubbing, but that's about it). Also, you cannot transfer song titles when recording - titling every song manually by pressing a couple of tiny buttons? I have better things to do with my time, thank you very much
4. Flash-based MP3 players - the pluses are their small size and lack of moving parts. The drawbacks, however, are quite significant. First, the storage media used in most players is extremely expensive (go to Pricewatch and check out the prices for a 128MB CompactFlash card or a 64MB SmartMedia card, then figure out how many songs you'll be able to fit on one - not that many, especially if you use bitrates above 128kbps). As a result, most people won't be able to afford more than a couple of memory cards, which pretty much ties you to your PC. Going on a trip? You'd better REALLY like the 15 or so songs you've loaded into your MP3 player. If you want sound quality that will approach that of an MD player, you have to use higher bitrates (192kbps and up), which will limit the number of songs you can load at one time even further.
Second, the currently available MP3 players are still not up to par with CD or MD players as far as sound reproduction quality is concerned (crappy bass, distorted vocals, etc). The third drawback, and I realize that this is not a concern for some people, but it is for me - all MP3 players I've seen so far look and feel cheap. The Rio 600 is a step in the right direction, but they put on this rubber coating which will peel off in a couple of months...ugh.
5. HD-based MP3 players - presently there's only one available (the PJB), but Creative has one coming out in a few months. I haven't seen the one that's available, so I can't comment on it, but from what I can see now, the main problems are the size and the price - the PJB goes for $600, while the Creative Nomad Jukebox will go on sale for the low price of $400
6. MP3 players with other storage options - again, don't know much about these, supposedly there's a unit coming out that uses Clik disks, those are cheap, but can only hold 40 megs, so I see no real advantages over a MD player.
To summarize, there is no best solution, it all depends on what you want from your portable stereo. If price is the primary consideration, your best bet would be an ordinary CD walkman, or, if you can wait a few months, a hybrid CD/mp3 CD unit.
If you lead an active lifestyle and want a portable stereo for jogging/working out, then get a MP3 player - they are tiny, skip-proof and since you won't be venturing far from your PC for prolonged periods of time, limited storage isn't a big consideration. Also, if you have a digital camera and are going to invest into CompactFlash or SmartMedia cards anyway, might as well get yourself a MP3 player. Finally, the build quality of MP3 players is getting better and better, compare the first Rio and the latest (Rio600), so I think that in a year or two most MP3 players will lose the "garage-brand" look and feel.
As for MD?it's kinda in-between the two - it allows digital recording from a PC (although for that you need a USB to optical adapter, $100 for a Xitel DG-1, or about $250 for a Roland model), it is smaller than a CD player, uses cheap storage medium and offers sound reproduction quality that is pretty much equal to that of a CD player.
Some MD units look extremely cool - a friend of mine bought a Panasonic Shockwave series MD walkman when he was in Japan - the body is made of titanium, and it looks awesome...