Anything cheezy, commercial, and recognizable. It's nice to have a video that puts a new look on a song, like having whats her face singing "I WILLL SURVIVE!!1!!" while you run around killing stuff for 5 minutes. I have made a video that is set to Twinkle Twinkle Little Star, and it's the most badass thing ever. Synchronization is key, so try not to use a lot of Heavy Metal, tough to sync those complex riffs. Try using some house tunes, and techno stuff, but it shouldn't be too repetitive.
If you can tap your foot to it, sing along with it, or both. it's gold.