Yeah you can randomize play in iTunes or Zune, but you have to make arbitrary playlists explicitly. You can drag tracks around in VLC but the UI isn't helpful.
I would say I knew 90% of the songs in my music collection then and probably know 10% now despite it being about the same size, purely because of a few 'helpful' UI constraints.
People sort of suggest that music changed when MP3s and Napster bloomed, but the 'end of an era' in my mind, the time when my experience of music definitely changed, is when I was obligated to stop using Winamp and start using iTunes etc in the mid 2000s.