MP3 allows maximum portability as practically all pocket music players support it, but there are a number of other formats like the iTunes mp4 format (or m4a, whatever you want to call it) which enjoy some support.
CDEX is a good CD -> MP3 converter, I believe it can do a number of other formats but I've not looked at the list in a while. I just use the built in Lame MP3 encoder. It is extremely configurable to your quality needs so you can decide for yourself how much quality you are willing to sacrifice.
http://cdexos.sourceforge.net/
Ah, here's a list of supported formats:
Lame MP3 encoder
Internal MP2 encoder
APE lossles audio format
Ogg Vorbis encoder
The Windows MP3 encoder (Fraunhofer MP3 encoder)
NTT VQF encoder
FAAC encoder
Windows WMA8 encoder
My personal preference is to set CDEX up to Lame MP3, VBR encoding (32-320kbps) with quality set to 2. This gives files that average at about 192-220kbps but also try to keep as much quality as you can while not slowing down to a crawl. With quality set to 1 it slows down tremendously. The VBR is useful for quality too as some sections of music do not need as many bits to encode as others and so are encoded with less which means more bits can be used in a section that needs it. I am oversimplifying but it's all you really need to know.