If you have the space, there's Apple Lossless, which takes IIRC about 300 MB per CD. Caveat, the format is closed proprietary, but third-party codecs are in the works.
I don't have an iPod yet--my sister has one. And I don't think she'd be too happy if I threw Linux on it. 8^)