You should tweak your selection options when selecting the background you want to use. Be a bit more aggressive with it (i.e. slightly higher tolerance and enable anti-aliasing). Then, when you add your outline, do so using a style on the layer. In Photoshop this would be an 'outline' with the default 3px weight. You can try having the outline originate on the border of the image going both inwards and outwards rather than only outwards (the default behavior).
I know you said you use Gimp but I would be shocked if Gimp didn't have this same feature.
I know you said you use Gimp but I would be shocked if Gimp didn't have this same feature.