If you look closely at the background of a painting, it's not flat. It has variations in color, and there is more going on than just the brushstrokes. There are also patterns of light and shadow, and sometimes even of walls and corners. Here's an easy way to do that in Photoshop, so that your backgrounds can have a more natural look.

I'll use bright colors in this example, so that what I'm doing will be obvious. Even so, we end up with a dark background that will focus attention on the foreground. Your choice of color will affect the overall contrast and mood, so feel free to experiment.

This is one of those things that is boring, but very useful.

To start, set a background color. In this example I'm using black for contrast, but you can really do anything you want.

Set your foreground and background colors to the end values of a range that you want to use. Add a new layer just above the background. Select a rectangular section of the image, and do a gradient diagonally within the selection. Invert the image, and do another gradient. I'm putting the light section in the center and the dark section in the upper corners, to help focus attention toward the lower center. Deselect.

Apply Gaussian blurs of 8, 4,and 2 pixels.

Add a layer mask, and render clouds in the mask. A Gaussian blur can help; this one was blurred three pixels.

You may want to render clouds in the mask more than once, until you get a pattern that works for the image you want to do with your background.

To get a final background, lower the layer opacity level. This one is set to 60%, which lets the black background layer show through.

If you need to do additional editing at this point, you can always use image adjustments for color, brightness, and contrast. This was used to generate the background in the Last Supper.