The mp3 format doesn't support true gapless playback; I don't know about WMA. Some players include a crossfading kludge, which is good enough for a 'live album' but obviously unacceptable for CM. What I'm waiting for is a player that supports the open-source Ogg Vorbis format, which is designed for gapless playback.
Neuros Audio has a portable player in 128MB and 20GB flavors. They'll be releasing Vorbis and Linux support as a user-installable upgrade. The product specs at
http://neurosaudio.com don't mention WMA, just mp3. Their USB is 1.1, which is a bit puzzling for a product released only this year.
Ogg Vorbis support is coming later to portables than to software players because Vorbis playback uses floating-point processing that portables typically don't have. There are a number of PC and Mac players that support the format, including Winamp (since version 2.80, I think.)