Feasibility of generating large images with a convnet
The way you would recognize images (image -> genre) would be very different from the other way around (genre -> image). For the former you are correct on what would be involved.

For the latter, if you want large images then GANs are indeed the way to go. Currently the largest images we can generate are on the order of 220 x 220 pixels, mostly due to memory constraints on the GPU. There is no fundamental problem with having rectangular images, it just so happens that we use squares. You would be able to use identical architectures to train on rectangular data as well.

The reason that some generated images you see (e.g. from DeepDream or NeuralStyle) are larger is that it's not a GAN. Both of these are not generative models in a standard sense, even if they do technically "generate" images. Instead, they merely modify an existing image by running backprop on a specifically designed loss function.

TLDR: your movie genre recognition idea is sound. For generation, have a look at things like this (https://github.com/Newmu/dcgan_code), where Alec generated album covers instead of posters. If you have enough data it will do something half sensible.