Solid foundation appears to be the most popular in American English, judging from this graph. However, the Ngram search doesn't distinguish between different meanings of these phrases, so it’s not a reliable guide by itself.
Here's one way to think about this: notice that when applied to a person’s education and prior experience, foundation and background are both metaphors, even though they're nearly-dead metaphors. Literally, a foundation is something solid that you build upon, such as the foundation for a house. Literally, a background is the part of a picture that contains scenery or context for the objects depicted in the foreground. The term solid foundation is used literally in construction, and metaphorically for many, many different things.
So, it shouldn’t come as a surprise that solid foundation is the most common of the four and solid background is the least common. Solid foundation makes the most literal sense and solid background makes the least literal sense.
You asked which phrase is most common, and that’s hard to say for the reasons just explained. If you’re mainly interested in which is the best for describing a person’s education and prior experience as they relate to doing a new job, here is one native speaker’s view. While solid foundation makes the most sense, I find the word strong to have a slightly more positive connotation than solid, and to stand out a little better—maybe because it’s used less often. Overall, I'd say that solid background is the weakest of the four phrases, but they’re almost indistinguishable. Other people will perceive the same phrases slightly differently, of course.
Note that the most common phrase might not be the best. In fact, a more-common phrase can be weaker because it’s so common.