www.alphadictionary.com

'Common or garden' is a mainly British idiom meaning 'ordinary'. It need not have anything to do with gardens (e.g. "a common or garden computer"). It is always used before a noun, and may be hyphenated (common-or-garden). Its general use dates back to the 1880s.

I am interested to know how its 'non-garden' sense arose. Also, in its original sense, was 'common' an adjective (as in "a common variety and/or a garden variety"), or was it a noun (i.e. "as found on commons or in gardens")?

I note in both yr examples, "variety" is the noun modified. I don't believe I've ever heard any other phrase than garden variety (or common v.). I would assume garden equals common because the usual garden has common vegetables or flowers. British English confuses me because they insist on using garden to mean yard, as in a front yard with grass. When I read that a garden lies in front of the house, I picture flower beds that bloom in season.