I know this is going to sound like a DUH!!! comment, but the 6900 also has a TRUE shuffle random play mode....it jumps all around the folder heirerchy to play random songs.
Still havnt attempted the playlists however.
BTW, Im over 30 gigs now, and the 20 sec initial seek time has not gone up