If your hardware supports Ogg Vorbis then I'd go with that over mp3.
Reasons:
Ogg Vorbis -q 6 or 7 should be as good as lame -V 0 in practise so you can have slightly smaller files.
Really simple tagging, identical to flac. No silly restrictions on custom fields or genres.
Native gapless. It's not a workaround, it just works as expected.
Very simple command line encoder. That might not matter to many but it can make life super simple with commands, scripts or apps that call a command line encoder. It's very neat the way it works with flac to copy all the metadata automatically without needing another tool. For example the command 'oggenc -q 7 *.flac' creates high quality oggs from all flacs in the directory and all the tags are copied too.
Replay gain always works on the tags, never by changing the audio (replaygain on mp3 can do either).
Disadvantage: embedded cover art not officially supported, there are a couple of different ways it can be done and different players can choke on either or both.
Both mp3 and ogg are old codecs now and can both run into problems with some samples. aac probably is a better choice for high quality, low file size and lower chance of encountering a sample that defeats its psychoacoustic model. If your hardware supports gapless m4a then you might be better off with aac than any other lossy codec. Apple, Fraunhofer and Nero are all good aac encoders, and in that order (see Hydrogen Audio for confirmation by listening tests) so you can use iTunes or Winamp or fdkaac, which covers encoding in Mac, Windows and Linux/BSD (and Android) nicely.
The above isn't comprehensive, just some thoughts, and I might have failed to think of something significant.
But if you have plenty of storage on your player why not just use flac? I saved 100s of GB storage on my PC and backups by only using flac where possible (no longer keep a mirrored lossy version of my rips).