(1) Parent categories > sub-categories.
DVD > Horror
DVD > Comedy
Theater > Horror
Theater > Comedy
(2) Each post in more than 1 category.
each post in either DVD or Theater cat
PLUS also put it in a Genres > Horror type of cat.
(3) Or, this idea isn't as good to me but if you want, make your cats DVD and Theater,and get a "Tags" plugin for tagging all those other genres.
As for The Loop, there's no need for me to explain it. I can't write it out as clearly as it's already written in the Codex (which is the Docs page on this site). Search there for The Loop, and on that page look for info about limiting which categories The Loop pulls from.
To prove to yourself this would work just try putting &cat=2 at the end of your homepage URL in your browser. This action, you can build into your template.