You're spot-on with the need to shift some parts of the red/cyan layers either more or less in order to achieve the control of the separation that you're after.
One way to do it, if we're assuming that you're starting from a single 2D image, is to isolate different elements of the image onto their own layers, such as the background on one and the lamp on another. This might require some careful selection, and even some "mending" (clone/heal in Photoshop) of the background in the areas which are "behind" the lamp.
Once you have the two parts, do the red/cyan separation as you did before, but separately for each part. Now adjust the background by only a small amount, and the lamp by a larger amount. Or you could leave the background alone and just do the lamp, or even adjust them in opposite directions - some trial and error is necessary here.
You will now have a composite image where the lamp stands out from the background, which is one step forward. However, if you look at the floor under the base of the lamp it is still "flat", i.e. it feel like it's all at the same distance from you. This requires another red/cyan pair with just that part of the image, but this time you'll have to distort the layers rather than simply shift them, such that the part of the floor which is closer to the viewer moves further apart than the part which is at the base. I'm not sure what tools you have in Paint.NET, but in Photoshop I would again use clone/heal to fill in more of the areas of the floor "behind" the lamp's base.
[edit] If you want to get really adventurous, you can use tools such as Liquify to fine-tune the degree of shift between the red and cyan layers; that way, you can adjust more complex elements, such as the round part of the lamp, and bring the front of it closer and the back of it further away. Again, this is most easily achieved with a separate pair of layers for just that area, so you can restore information "behind" it on other layers.
It also helps if you group the pairs of layers so you can turn them on and off easily. That's so you can work just on the element of your image that you're interested in.