Fuze, Clip and Clip+ all support m3u playlists. The original FW on all had some bad randomization issues, but it was drastically improved on all quite a while ago.
BTW, my primary listening mode is large m3u playlists on shuffle. So I’m pretty familiar with this aspect and am quite happy with it.
The only catch with m3u playlists is that the paths in the playlist must be relative to the location of the playlist.
For example, if the playlist is in the root of the player, the paths in the playlist need to look like:
Music\Artist\Album\Song.mp3
If the playlist is in the Music folder on the player, the paths need to look like: