I reckon our dummy example seems a bit simplistic considering the question I'm asking :P
I think the Taxonomy approach is a very good one (you're talking about Contrib.Taxonomy right?).
Assuming we have a page where users select a Color from a list, we could then use TaxonomyService.GetContentItemsQuery(TermPart, null) to retrieve all Content Items with the given color.
My biggest concern is, performance wise, does anyone know if there a big difference between:
ContentManager.Query("Fruit").Where<FruitColorValuePartRecord>(fc => fc.Id == OrangeColorId)