Everyone else has given good advice. The easiest meal for vegetarians is breakfast, and buffets are generally great for everyone (Boma is the best, IMO). Even a place like Biergarten worked well for me; I had plenty to eat and my omnivorous DH was VERY happy with his massive beers.
Counter service isn't too bad; these places have much less leeway to "vegetarianize" something, though. In Epcot, Tangierine Cafe and Sunshine Seasons have good choices for meals and of course there are snacks aplenty in World Showcase. In MK I like the Main Street Bakery and Columbia Harbour House. Rosie's in MGM has huge veggie burgers (they're soy, like Boca Burgers, which I'm not that fond of), and I would check the other CS places to see if there's anything that appeals to you. In Animal Kingdom, your CS choices are cheese pizza at Pizzafari and a veggie burger at Restaurantosaurus (and I think Restaurantosaurus fries are McDonald's--not vegetarian). Oh, and a fruit plate at Flame Tree, but I think it comes with yogurt--which may have gelatin. AK is very poor for vegetarians for CS. I would probably go to Tusker House or Rainforest Cafe or eat a light lunch and save room for Boma at dinner. Avoid Yak and Yeti--I have yet to see a vegetarian review it positively, either TS or CS.
