I don't think there is really a right answer, it's all preference. A few forum members, like Mary K or day Vies, could combine teal and burgundy to perfection but I'd feel really odd. If you are trying to get away from black, then one of the color choices would be good. I like grey with black, navy, teal, and burgundy. If your feet are likely to shrink back, pick the color that plays well with more of your wardrobe.