And soy will be your friend!
soy milk is good in almost all cream soups, especially potato leek, tomato, and soups with corn.
there is also rice milk, less protien, I haven't used it much, but you could give it a try?
There are soy and rice pastas. they are quite good, just note different cooking times.
And here is a mock feta cheese made with tofu. I make it when I have people with lactose problems and the rest of the crew likes it too.
Mock Feta Cheese ( Vegan Substitute ) Recipe : Recipezaar
again I posted the link because the reviews are interesting. Also, this is a huge source for recipes--just enter the main ingredient or name of dish you want to make and click into vegan, or wheat free, or dairy free.
Also the Whole Foods website is great for recipes and has sections with your parameters. And the Vegetarian Times website.
Nan