Is video possible with arduino?

I would like to have video on a display for my upcoming project with arduino, it would not have to be good, maybe 15-20 fps. I would also need to display a variety of colors. Is this possible and if so, are there any recommended displays for it?

Not a chance. Arduino is far too slow and has far too little memory.

The Raspberry Pi would work.

AFAIK only a grayscale video streaming has been done with a DUE.

A video of the result: 160x120 - YouTube

The full project: Articles by Sergiy Bogdancev (Articles: 8) - CodeProject

There's some Teensy projects with impressive video or video-like effects on large screens built out of LED strips. That is a fairly ambitious project.