MiniDisc is a relatively new audio recording technology from Sony which, IMHO, combines the best parts of CDs and tapes. It's digital, which means that it retains the quality of CDs, as well as being indexable by track, just like CDs, but is also re-recordable, like tapes, making them extremely useful. They hold 74 minutes of music (or double that if you don't care and want to record in mono, rather than stereo), just like a CD, but measure only roughly 2.5 inches square. The physical medium itself also comes within a plastic case which you insert into the player. This case protects the disk from shaking around too much, which cuts down on skipping while running, etc.
As of yet, not many albums have been released to MD, but buying CDs then transferring them to MD is easy. You can also take the audio out from your computer and thereby record MP3s that you have onto MD. The recording device is quite smart and interprets breaks in sound as intended track breaks. The most expensive portable player/recorder on the market right now is about US$250 and MiniDisks themselves cost about US$3 each. Yeah, that's expensive per disk, but remember they're re-recordable and that price will almost certainly drop if the format catches on.