How to calculate a good background for a small image? (procedural background)

I want to frame favicons. A size of a favicon is usually 16x16 (could be bigger). The frame would be 160x100. Favicons have different shapes and colors (I don't know ahead of time what favicons look like), and I'd like to compute a good enough background. Could be plain color, could include stripes/patterns.

There are naive ways to do that (compute dominant color and derive background color with good contrast), but I'm wondering if there would any smarter way to build a nice background.

Think about Chrome's new tab page, but instead of screenshots, framed favicons:

Some favicons for reference:

Example of naive framing (colors chosen manually):