Ogg (-q 6 or 7) is the best format widely supported on portable digital music players, IMO. MPC/Musepack is the best lossy codec, period. I use FLAC when I initially rip a cd, which I can then transcode into whatever lossy codec I desire.
Last is MP3 with --alt-preset-extreme (preferred), or --alt-preset-standard VBR modes.
I have a Sansa Fuze 8gb coming from Amazon next week, luckily it supports both FLAC and OGG, which is the format most of my music is in. I used to use MPC almost exclusively, expecting portable digital players to start supporting it due to stellar audio quality. But it never really took off in the mainstream so I re-ripped my CDs as flac for archival purposes and then transcode those to OGG -q 7 for general use.