It shouldn't matter what order you apply these operations in. MP3gain performs its calculations and writes the result to APEv2 tags in the MP3 file, so the actual audio data isn't altered.
If you have a particularly braindead encoder, it may apply the gain change during decoding, in which case you'll end up transcoding the gain-altered audio data. (This would be a Bad Thing(tm).) You could use an audio editor program like Audacity to examine the waveforms directly to determine whether this is the case.
Most likely, transcoding will fail to copy all the metadata from the original to the re-encoded MP3, so you'd need to run MP3gain on the transcoded files anyway.
If you're really concerned with audio quality, don't transcode your files. Re-rip the CD into the bitrate you need -- or better yet, rip to or purchase as a lossless format like FLAC, and then encode MP3s to the bitrate you need.