Translation:What would you recommend to a vegetarian?
Is the to really needed? I'm afraid the answer is yes and my English is getting lazy and sloppy. But asking just in case :)
It is. Recommend is a transitive verb so "recommend a vegetarian" means, that you suggest, that it's the vegetarian, who should be eaten.