If it were me, I would just use a higher bitrate MP3 with a really really good encoder.

Other formats like Ogg are great, but those formats mostly only shine at low bit rates. For example, if you compare an Ogg and an MP3 at 128k, sure the Ogg is going to sound better, but if they were both at 384k (and assuming your MP3 encoder isn't rolling off high frequencies too harshly), you're not going to hear any difference.

Also, any formats beside MP3 are going to be less compatible with other devices that may come along in the future, which is one of your criteria. If you want the most compatibility with the most devices and software, MP3 is currently still the way to go.

I just got done with a great big re-encode of my collection and I chose 256k constant bitrate MP3 via a Fraunhofer-derived encoder. I'm very happy with my choice.

One of the things that sticking with MP3 allows me to do is to apply a plethora of software tools to the collection for managing the files. There are so many MP3-specific tools for editing tags, adding/displaying lyrics, cutting and splicing, organizing, scanning, etc., that I can't imagine going to another file format even if is somehow subtly better in the audio reproduction.