There is a plugin called “Automatic YouTube Posts” that works pretty well. I used that and made my video category display as a gallery. I also have a random video show up on the main page every time the page loads.
Video Gallery
Random Video Display (in sidebar)
In order to do this you have to make use of the video thumbnails. Basically, I created the gallery by just making the video thumbnails be posted into a <div> in a loop. I can copy the exact code I wrote to do this, but I just wanted to let you know that it is possible.