I live in Huntsville, and I think we have plenty of veg-friendly restaurants, although vegetarian-only places seem to be rare and short-lived since our long-standing one closed a few years ago. It is extremely easy to find places as a vegetarian, and while somewhat more tricky as a vegan, it's still very possible. I think having a Seventh-Day Adventist university in town definitely helps make us a more veg-friendly place to live.
Some of the best local places:
Bandito Burrito. I've only been to the Governor's Drive location so I don't know about the others. Very vegetarian friendly owner and staff; clearly marked vegetarian menu. If you are vegan you can order with no cheese. You must try the green bean burrito (green sauce, not green beans.

) Plus, everything is really cheap.
Thai Garden is located in Five Points on the corner of Andrew Jackson Way and Wellman. The food is just incredible, and they are so veg-friendly. Don't be deceived by the four-item vegetarian menu; look for the menu items that offer a choice of meats and you can just ask for tofu instead. Great stuff!
Curry in a Hurry is a Carribean restaurant on Jordan Lane. It is fabulous, and the owners are SO nice! They have a large vegetarian menu with lots of options like mock chicken (which I think is seitan), tofu, chickpeas, and delicious veggies. Served with rice and salad. My favorite is the jerk mock chicken, but it is really spicy; the curry mock chicken is better if you like milder food. I also love the vegetable dishes. It is kind of easy to miss, so look for the shopping center with the Dollar Store in it.
Stanlieo's, as mentioned. Super vegetarian menu using a variety of Worthington meats. You can even get a veggie reuben if you are so inclined (I'm not!

). Subs come with cheese and mayo.
We have two Indian restaurants on Jordan Lane: Vinny's and Sitar. They are both absolutely amazing, but I don't know about the vegan status. Both have lunch buffets with tons of veg options. The buffet at sitar is larger. Both are wonderful for dinner. Everything is good.
My favorite Chinese place is Golden Star on Oakwood Ave. Good tofu options, and the fried rice is not made with eggs.
We have lots of great Mexican restaurants. Most people seem to like Rosie's, and they have a nice vegetarian menu with things like veggie quesadillas, but personally I just can't stand their food. My favorite is Casa Blanca; it also has a nice vegetarian menu with standard offerings plus fresh spinach fajitas. I think it is delicious. Try the pineapple or peach iced tea.
Papa Gyro's on University has Greek food with tons of veg options. The falafel wraps are great, but everything I have had there is superb, including the numerous options for plates and the veggie burger. Pretty much everything comes with dairy but many items can be ordered without. The owner is extremely nice and used to be vegetarian, so he is really understanding and happy to help you pick out something you will like.
Jamo's on Jordan Lane also has great Mediterranean food. The falafel wrap and veggie wrap are really good, and they serve my favorite hummus. They have a veggie BLT made with Morningstar bacon that can be ordered without mayo. They also have great coffee, smoothies, and fresh juice.
Plus we have all the usual good chain restaurants like Jason's Deli, Ruby Tuesday, Salsarita's, Moe's, Nothing but Noodles, etc.
Garden Cove Produce is on the corner of Pratt and Meridian is a pretty good-sized natural foods store. They have tons of veg grocery items, so if you are having a hard time finding something like nutritional yeast or bulk TVP, go there. I haven't checked lately, but last time I stopped in they also carried Vegan Gourmet cheese. Usually there are oodles of special vegan goodies to choose from.
We do have a vegetarian society here, and I have a card somewhere with the contact info, but I don't know anything about it.
That's all I can think of off the top of my head! Nice to meet you all. I love living in Huntsville and I would be happy to help if anyone has questions about the city or needs directions to some veg destination.