Gaplessness....

[simbun]

Lossy support is a nightmare; MP3 with ID3v2.3 is probably best supported, but it's horrible, everything else I've had problems with.

MP3 and AAC don't natively support gapless playback (in the spec), but LAME came up with a way to support it in MP3 as did Apple in AAC (and maybe other sources based on the bug tracker you linked to), but it only works if all decoders support it too.

Are you tied to iTunes, and do you have lossless versions of those lossy AAC files you have?
A simpler option would/should be OGG Vorbis as gapless playback is built into the spec, but it's not supported by iTunes.

At the end of the day you'll have to try them all (MP3, AAC, Vorbis) with each hardware/software player you have, to work out what's best for you.

I've settled on OGG Vorbis for portable use (FLAC for everything else), and even then my Fiio M5 (used only for running) doesn't show any Genre!