I'm vegetarian and rode cross country on the Northern Tier a couple years ago. My basic advice is be prepared to carry more food. I had a four pannier setup on that tour but I normally just use two front panniers and a saddlebag so I had a lot more space. I devoted the main compartment of my front pannier to food which let me carry a decent amount so I could stock up. I found, with only a few exceptions (East Montana for instance), there would be something close to a supermarket every four days or so. So I would stock up on my basics plus a few things for the next couple of days and then use the small town stores to supplement with more perishable things like cheese, fruit and vegetables (if available). I carried dried things like rice and beans, but I like to spend time cooking each evening (especially when you are camping at city parks and such where there isn't too much else to do) so I carried staples that in a pinch could serve as a meal and supplement it with what I could find. This all could be done vegan I think, many of my meals pretty much were.
In the midwest on the Northern Tier, which I imagine will be similar to the Midwest on the TransAm in the tiny town stores it'd often be pretty hard to find much vegetables. So worth carrying more of those when you can find them. I also found that even things like vegetable soup would usually be the kind with beef broth. You always can find bread, peanut butter and cheese of varying quality. Tortillas are usually pretty available and less bulky then bread. Mac and Cheese is usually available. Plenty of eggs if you are willing to eat those. The other problem I had was finding veggies in small quantities, even the big stores in the midwest would only sell things like carrots and such in big bags. Often I'd get those bags of pre sliced things so you could get less. Getting things like Tofu I could only really do in towns with a coop as if a big store even had it, it be some huge package.
At restaurants I think vegan would be harder. Grilled Cheese can be had if you ignore what it's going to be grilled on. Pancakes, waffles, fried potatoes likewise. That old standby salad is harder to find in the midwest and will usually be iceberg lettuce based. That being said I was occasionally surprised by some little town being hipper than you'd have suspected, or some random looking diner having a sautéed veggie sandwich, or a good coffee shop that might make pannis or some such. But you can't bank on that at all.
