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.