The Remote Solutions Personal Jukebox looks to have been the first of the models to use a laptop drive instead of small and expensive flash, but at $799 for 4.8GB, it was very pricey (1999).
The Creative NOMAD Jukebox in late 2000 had 6GB for $429.
In late 2001, Apple introduces the iPod, which at 4GB for $399, is actually not quite as good in a dollar per GB metric.
I think it's clear that it's not really the idea that made the iPod take off, but the marketing, polish, and IMO most importantly, that they had a real software company work on it rather than a bunch of EE people. Not to denigrate electrical engineers, but often it's a different type of programming that goes into UI and UX, and having people that have worked on that for years can matter quite a bit.
1: http://www.pcworld.com/article/174725/evolution_of_the_mp3_p...