I would suggest exploring the cuisines of cultures that are predominantly vegetarian. I was very much a meat-and-potatoes person growing up in the American Midwest, and I haven't moved completely away from meat-eating, but I eat far less now because I learned how to cook Indian, Thai, and Vietnamese food at home. Cuisines where vegetarianism isn't a second-class citizen tend to put more effort into making good-tasting vegetarian dishes.