And while we're at it, is light a particle or a wave? That one, we already have (sort of) an answer for: it depends on how it's constrained. The same, I think, applies to anime too: it's a genre and a medium, depending on which way the pie is being sliced, and who's doing the slicing, and who's doing the serving of the slices.
To me, the main distinction is in which eyes are doing the beholding. If you're a fan, it's easier to think of anime as a medium, because odds are you've spent enough time up close and personal with it to see how it manifests in too many different ways to be a genre. If you're a non-fan, looking in from the outside, many aspects of it tend to blur together to present to an outsider the trappings of a genre.
Some of this, I suspect, comes from the way anime — more these days than before — is contrived to serve a certain self-selecting audience that expects to see certain things. Hence the endless parade of harem and moé shows — not that those things are automatically bad, more that what we get is designed more to fit a certain set of preconceptions than it is to tell a story or even be all that entertaining. (I'm glad the worst of those two trends appears to be over, but I'm not confident it's being replaced with anything markedly better.) A non-fan looks at such things and sees a whole slew of traits that s/he can bundle together into a genre — making it all the easier to identify it on sight and, most likely, consign it to perdition.
Fans on the inside, though, see genres within anime, but they don't automatically regard anime as a whole as a "genre". They know that it's a container, though, one which can enclose any number of different sorts of experiences. Nobody with enough experience thinks the works of Satoshi Kon, Clannad, the various Gundams, or the various Monogataris are coming from remotely the same places. Odds are no two of those things even have the same fanbases within anime fandom — but again, to an outsider, it's all one big undifferentiated lump of Weird Japan. Labeling it as a genre makes it easier to not have to think about the possibility that it might in fact be not all that undifferentiated.
Understand something: I'm not blaming anyone for taking that approach. Most anyone outside of any highly trafficked fandom is going to feel baffled. But few people that I've run into think of Doctor Who, Red Dwarf, and Sherlock in the same "genre" of British Stuff I Couldn't Be Bothered With. I suspect that's because the main mode of delivery for those things didn't necessarily start with its national origin, but with a concept. Anime is set apart first and foremost by the fact that it comes from Japan. If the West put one big label on it to begin with as a way to allow "us" to wrap "our" heads around it, is it really such a surprise that so many of those not deep in the thick of it are able to put it all in a box and sit on the lid?
I suspect the same goes for all those who can't get into Hong Kong action pictures, or Bollywood musicals. And, while we're at it, what about all those abroad who might well have the same shelve-it-and-shove-it approach to Hollywood tentpole productions (which might well all be a "genre", given how formulaic they are), or the Marvel/DC axis of comic books? If people can call anime a "genre", it's not because of anything anime alone has done; it's because of the way many of the mass-market entertainments created by any culture tend to breed in a good deal of uniformity that only falls away once you come closer.
What I'm saying here, then, is that the whole question of whether anime is a genre or a medium doesn't just depend on who you ask. The very fact that such a question exists is a symptom of how any of us looks at another culture's cultural products, and maybe even our own as well. (Many Japanese novelists, for instance, give anime and especially manga the same lump-it-together-and-forget-it treatment as Western non-fans.) We have a hard time not looking at such things without needing a label or a box of some kind, in big part because such things are consumption instructions. If we know something is comic-book-ish, we have some idea of how to process the material. If we know something is anime-ish, likewise.
But those instructions are not absolute. They don't come down from the mountain on stone tablets, as it were; they come from the whole history of viewership for those things. They don't have to be taken on face value, and most of the history of anime advocacy between fans and from fans to non-fans revolves around this. It's not just a cartoon, we say to the wholly uninitiated. And to the initiated who already has some territory staked out, we tell them it's not just a love story or a fight show. We would scarcely need to do this kind of advocacy if the existing labels — harem comedy, shōnen action show, shōjō romance — didn't already carry such weight.
What's more, neither mode — genre and medium — exists entirely apart from the other, certainly not as long as either viewpoint exists at all. Some anime embody anime-as-a-genre far more specifically than others, and ask to be looked at in that light; some embody it far more as a medium than others, and so that approach works best for the items in question. The genre tells us what kind of story to expect, and how it will be fulfilled. This medium is a way to look at something that empowers it in certain ways, that gives it a certain automatic suspension of disbelief that some stories need to embody as effortlessly as they can.
Knowing that we have these reactions puts us one step closer towards being able to approach these things entirely on their own terms, without needing to figure out first what part of the shelf to put them on. In the end, we don't need a label of "genre" or even "medium" to justify anything; it's the labels that need us to justify themselves. Would that we can see so.