It is actually not hard at all. Some recent studies (don't have references, sorry) showed that you don't need to get all of your essential amino acids in a single serving so there is no real need to stack your meals to contain a complete protein. The key is that on average you get all of your essential amino acids which, except for one or two (in recent debated studies), you can't really overdose on.
Another study showed that it is actually really hard to not get all of your amino acids in any diet. Since just about every food you eat has some combination of amino acids in it, unless you are eating literally the same thing every meal of every day you are incredibly likely to get all of your essential amino acids on a daily (and even likely a per meal) basis.
The study I read indicated that the author couldn't come up with a reasonable "average daily meatless meal set" that did not contain all of the essential amino acids throughout the day. The same goes for a vegan diet.
Unfortunately a while back, when vegetarianism and veganism hit off there was the incorrect belief that you needed to get complete proteins in a single sitting. While this has since been shown to be incorrect, it seems that it will forever fuel the fires of anti-vegetarianism debate.
I also don't have references, but I believe this is only true for diets mostly composed of Real Food. I seem to remember that in the past, foods with gelatin as the main protein have caused fairly widespread amino acid deficiencies among those who ate a lot of processed foods. Not that I would recommend this in any case!
(Note: I wasn't quite sure whether this warranted a high level post or just a discussion. I haven't made a high level post yet, and wasn't entirely sure what the requirements are. For now I made it a discussion, but I'd like some feedback on that)
I've been somewhat surprised by the lack of many threads on Less Wrong dealing with vegetarianism, either for or against. Is there some near-universally accepted-but-unspoken philosophy here, or is it just not something people think of much? I was particularly taken aback by the Newtonmas invitation not even mentioning a vegetarian option. If a bunch of hyper-rationalists aren't even thinking about it, then either something is pretty wrong with my thinking or theirs.
I'm not going to go through all the arguments in detail here, but I'll list the basic ideas. If you've read "Diet for a Small Planet" or are otherwise aware of the specifics, and have counterarguments, feel free to object. If you haven't, I consider reading it (or something similar) a prerequisite for making a decision about whether you eat meat, just as reading the sequences is important to have meaningful discussion on this site.
The issues:
1. "It's cruel to animals." Factory farming is cruel on a massive scale, beyond what we find in nature. Even if animal suffering has only 1% the weight of a humans, there's enough multiplying going on that you can't just ignore it. I haven't precisely clarified my ethics in a way that avoids the Repugnant Conclusion (I've been vaguely describing myself as a "Preference Utilitarian" but I confess that I haven't fully explored the ramifications of it), but it seems to me that if you're not okay with breeding a subservient, less intelligent species of humans for slave labor and consumption, you shouldn't be okay with how we treat animals. I don't think intelligence gives humans any additional intrinsic value, and I don't think most humans use their intelligence to contribute to the universe on a scale meaningful enough to make a binary distinction between the instrumental value of the average human vs the average cow.
2. "It's bad for humans." The scale on which we eat meat is demonstrably unhealthy, wasteful and recent (arising in Western culture in the last hundred years). The way Westerners eat in general is unhealthy and meat is just a part of that, but it's a significant factor.
3. "It's bad for the environment (which is bad for both human and non-human animals)." Massive amounts of cows require massive amounts of grain, which require unsustainable agriculture which damages the soil. The cows themselves are a major pollution. (Edit: removed an attention grabbing fact that may or may not have been strictly true but I'm not currently prepared to defend)
Now, there are some legitimate counterarguments against strict vegetarianism. It's not necessary to be a pure vegetarian for health or environmental reasons. I do not object to free range farms that provide their animals with a decent life and painless death. I am fine with hunting. (In fact, until a super-AI somehow rewrites the rules of the ecosystem, hunting certain animals is necessary since humans have eliminated the natural predators). On top of all that, animal cruelty is only one of a million problems facing the world, factoring farming is only one of its causes, and dealing with it takes effort. You could be spending that effort dealing with one of the other 999,999 kinds of injustice that the world faces. And if that is your choice, after having given serious consideration to the issue, I understand.
I actually eat meat approximately once a month, for each of the above reasons. Western Society makes it difficult to live perfectly, and once-a-month turns out to be approximately how often I fail to live up to my ideals. My end goal for food consumption is to derive my meat, eggs and dairy products from ethical sources, after which I'll consider it "good enough" (i.e. diminishing returns of effort vs improving-the-world) and move on to another area of self improvement.