Main thing would be big post tiles next to average sized images in first page.
Side column for Ads
integration with social networks (twitter, facebook, RSS) prefferably with title/icon that display follower count
option to pull recent tweets and show them on page would be nice as well
Of course youtube and vimeo videos can be embeded in any theme, but if there is some special video embed support - it would be an advantage.
So far I found those themes:
They're great, but before I purchase, I thought maybe you - Themeforesters could suggest me some more.