Apple Lossless reduces the size by about 50% and will preserve the original resolution. Concerning MP3s, it is misleading to say they are of low quality. Yes, it is a lossy format, but one can choose any bitrate. Therefore, one can make near CD-quality encodings just as one can make extremely crappy ones. Unless you carry around highest-quality headphones or connect the iPod to a high-quality stereo system, AAC is perfectly fine. We are not talking about extreme audiophily here. If you choose MP3, you should go with at least 128 bits with variable bitrate encoding.
The iPod is fantastic. My only beef is with the cataloging of classical music. It is not (yet) straightforward to easily navigate around a large collection.