SusanV at fatfreevegan.com has a bunch of easy to prepare vegan recipes. Her enchiladas are AMAZING! Her Quinoa recipes are also amazingly rich and flavorful. Another good vegan author is Nava Atlas, who is currently working with Susan on a vegan holiday recipe book.
I do mostly vegetarian recipes at my site (http://dancingveggies.blogspot.com) but I also have a number of vegan recipes including a few desserts which most vegan recipe books are short of.
The main trick is just finding out how stricts of vegans are they: is honey allowed? what about what sugars? various extracts? There are so many flavors of vegan that you never know what you are going to get.

Try a quinoa salad. Follow the directions on the box. Whip up a vinaigrette, add fresh herbs, some chopped vegetables, toasted nuts or seeds, maybe some raisins or other dried fruit and serve on top of lettuce/greens.
You could also do a red lentil soup with it.
Something more labor-intensive that both egans and meat-eaters can appreciate is a eggplant stuffed with peanuts, sesame and other good stuff. The recipe is from a great cookbook called Five Spices Fifty Dishes. I found a variation online: http://markbittman.com/stuffed-indian-eggplant

there is a wonderful vegan cookbook out there called Vegan Soul Kitchen by Bryant Terry and it has some really good stuff in it even for the meat eaters of the world. It might be worth checking out. The tempeh, shittake mushroom and cornmeal dumpling stew is great. You could create a wonderful gourmet vegan meal from the recipes.

Sorry - here's the link to the soup if you want it http://globaltableadventure.com/2010/02/21/recipe-hummus-bil-kammun-chickpea-soup/ :)

I have a lot of vegan recipes (although you might want to check if they eat sugar or not - some do, some don't)...

I'm cooking one meal for every country in the world, so my recipes are international - a little bit of everything, from every continent :)

http://globaltableadventure.com/category/recipes-by-category/vegan-recipes-by-category/

The pic is of an awesome vegan soup I made for Algeria - made with chickpeas and harisa/harissa.

Lots of my friends are vegans, so I experiment a lot.
I love these recipes from Joy the Baker:
http://www.joythebaker.com/blog/2009/11/vegan-pumpkin-walnut-bread/
http://www.joythebaker.com/blog/2010/04/coconut-pineapple-vegan-banana-bread/

Not to plug my own recipe, but a butternut squash soup would make a great starter.
http://www.food52.com/recipes/6615_lemongrass_scented_butternut_squash_soup

A vegan pho or curry with tofu or just vegetables. Eric Ripert has a wonderful recipe for a beautiful tian in the Le Bernadin cookbook that could be served with quinoa or another starch. But really you could serve a fall staple like gnocchi with sage, mushrooms, etc. and that's vegan with a salad and sorbet for dessert. Oh mushroom pate for an appetizer.

Bet that red lentil and cauliflower soup would be good with a little bacon in it...

I love it pierino, that made laugh! Tree bark! love it!

Good ideas! Thank yer lucky stars they aren't gluten free too. :)

Thank you thank you, my cup runneth over! So many fantastic ideas! pierino and betteirene, you guys crack me up somthin' fierce!

Las Vegans! Slap-my-thighs funny! pierino, you made me spit sweet tea all over my keyboard!

My friend Sybil (Latin for "Vegan from Hell") is the type of guerilla who goes to Macy's and puts stickers on cosmetics that say "This was tested on live animals." Mercifully, she morphs into a vegetarian when we go out to eat because she knows that very few local restaurants and cafes know how to cook for her. I wish she'd let me off the hook so easily.

I've fed her tofu-and-vegetable stir fry on rice, barley-vegetable soup, all manner of cold salads, roasted vegetable and lettuce sub sandwiches, lettuce wraps and spring rolls, ratatouille pizza with awful tofu cheese on her version and these suprisingly good homemade black bean burgers

http://allrecipes.com//Recipe/homemade-black-bean-veggie-burgers/Detail.aspx

(for the egg, substitute 1 Tbsp. flax seed with 1/4 c. warm tap water whirled in a blender),

You could do black bean burgers, fries and coleslaw, with Tofutti for dessert.
Ratatouille with campanelle, garlic bread and a simple salad with oil and vinegar, and Tofutti for dessert.
A stir fry on rice, spring rolls, and Tofutti for dessert.
AJ's red lentil and cauliflower soup with roasted eggplant hoagies. Guess what's for dessert?

I'm reminded that Tony Bourdain referred to vegans as the "hezbollah" of the vegetarian faction. They're impossible to cook for. Just prepare some plain brown rice and season it with grated tree bark. Of course cooking for Las Vegans could be worse.

The author of "The Urban Pantry" had a similar problem--if you have her book, the recipe for potato gratin with cashew cream is super-delish and even this non-vegan loves it.

Here is an elegant silky toasted pasta in a mushroom based broth. I like it with spinach or poached bok choy.
http://www.food.com/recipe/toasted-angel-hair-pasta-in-shiitake-broth-188889

I made this recently for vegans with a lovely cuke salad that was an appetizing and perky contrast. This was so popular I was asked to bring it to a potluck.
http://www.willystreet.coop/recipe/cucumber_and_wakame_salad

For dessert, how about poached pears as they are in season, or do a vegan chocolate cake, they turn out very well.

Sylvia Thompson in "Food for Friends" has a tomato, eggplant and pepper sauce served over pasta that is vegan and amazing. It tastes meaty because of the eggplant and silky smooth because of the amazing quantity of olive oil that she uses. There is a nationally distributed vegan cake mix that is also delicious. I can't remember the brand name but next time I am in Gourmet Garage I will write it down for you.

BTW, if you search recipes here with "vegan" as the search term, you get 123 results. There are probably many more, as the search engine only looks for the term in the name, ingredients and key words (I think). ;o)

Agree that for cooks not experienced with vegan food, best to make things that are otherwise vegan, substituting a bit when needed. You can also serve some non-vegan items.

I think dessert is the hardest -- though many pies will work if you use vegan shortening, crisps are wonderful too. I am also a big fan of oven roasted fruit with ice cream (there are some wonderful dairy free alternatives).

A favorite bean salad, from Smitten Kitchen, though I use 1 can beans and 1 can corn and do include the cilantro: http://smittenkitchen.com/2007/04/tabula-beana/

Make the red lentil and cauliflower soup I recently posted, using coconut oil instead of ghee or clarified butter. http://www.food52.com/recipes/7020_red_lentil_and_cauliflower_soup Serve raita on the side for the omnivores present, if appropriate. Toast some cumin seeds in the bottom of a heavy pan, then make brown basmati rice in the same pan, with the seeds. Brown some cashews in a small skillet and stir them into the cooked scented rice, with a big handful of cilantro, that you've chopped. Serve with a lovely salad (might I suggest my Brilliant Autumn Salad, posted the other day) and some mint chutney. http://www.food52.com/recipes/7200_brilliant_autumn_salad For dessert . . . . an apple or pear crisp made using oil instead of butter. Now see? That wasn't hard. ;o)

Rather than trying to vegan-ize something that wasn't meant to be that way, I'd say pick something that's already vegan. Japanese food has a lot to choose from - miso--or anything fermented--carries a lot of the same umami that meat does. Same with seaweed. So maybe miso soup, rice with sesame-seaweed salt, an assortment of pickled vegetables, sweet simmered carrots with hijiki seaweed, oshitashi salad (minus the bonito flakes) or goma-ae salad...

I would suggest you check out the conscious cook. I saw the author demo a "cream" of celeraic soup that looked great. Also, you can try springs rolls and or potstickers with various fillings, as the dough generally does not contain egg/dairy etc. Also, I recently had coconut/flax seed wraps with avocado and other filings as well.

At a brunch I was just at they had a few great options. One was Chiffonade Swiss Chard with raisins a teriyaki kind of sauce. They other was a cucuber salad with a vegan "feta" like dressing. You could probably google something similar.