The problem with being the first to break ground is that if you don’t keep up you’ll be quickly copied, or worse, beaten at your own game.
About 6 years ago The Minibosses were the first real known band doing videogame tunes. They’re still doing it, but so are a slew of other bands. Only real problem with the Minibosses is they only have 2 studio CDs out. So if you want your fill of videogame covers you have to go elsewhere.
The Advantage has 2 CDs out with a crapload of tracks. They don’t step on too many of the Minibosses’ toes. After a while you get sick of the Megaman covers (everyone does them), so they supplement their CDs with classic tunes for dorks, like The Moon theme from Ducktails, Marble Madness, Batman, and Double Dragon II.
If you have any other recommendations for VGMusic bands feel free to leave a link in the comments.