I like Monkey Audio Personally, barring that, FLAC and OGG. Even better, FLAC with an OGG encapsulation. As for the question of which players support OGGs, try out the iRivers, especialy the H3X0 series. An H320 is perfect for me, just need to save up and get one. While MPIO have great sound quality compared to alot of other players, they really lack extra features and the ability to be recognized as removable hard drives making hotplugging a nightmare for linux users. iRivers however work flawless, as do the iPods, at least under Linux, but apple seems to prey on a market thats filled with uneducated consumers and use some dirty business tactics with their iPod sales so I tend to avoid them. For me its either iRiver or Archos all the way : ). You can check out Tom's Hardware for reviews on all brands, and types of portable music players to find out which supports which formats and whats the right one for your price range!
edit: to the Audio Interchange File Format response... I belive it is alot like wav on windows. They have RAW PCM formats but also some codecs that can be used on the audio file as well. The user is probably using a perceptually lossless codec which makes them THINK it's lossless, however, I myself, NOT being an apple user, I cannot verify this information...