Over at XaraXone.com the photo gallery we use is WP Photo Album Plus. It is free and you can download it from the plugin section at WordPress.org. I highly recommend it.

For displaying video nicely, we use JW Media Player by Longtail Video. You can use it standalone; it has a WP extension; and it is the main video engine for most of the video gallery plugins. JWMedia Player doesn't have gallery functions itself, other WP video gallery extensions take care of the gallery infrastructure, but actually use JWMedia Player to fetch and display the video.

JW Media Player is free for non-commercial use and reasonably priced for commercial use. As for the video gallery part, there are lots of them, and it really boils down to what exactly you need. The JWMedia Player plugin for WP and a wide assortment of video gallery plugins are available from the Plugins section of WordPress.org