Here's Wikipedia's constantly updated list of Virtual Console games for North America.
http://en.wikipedia.org/wiki/List_of_Virtual_Console_games_%28North_America%29
Gradius is already on there. Battle City and Dr. Mario aren't, but Dr. Mario will be downloadable for Wii Ware next year, with online battle modes and even 4 player co-op!
For your PS2, I highly highly highly recommend Katamari Damacy. It's under $20 on eBay, and I think new copies are only $20 nowadays anyway, greatest hits style. That game is loads of fun, and has the best soundtrack in the world.
You can download the free demo for the 360 version to try it out first though.
Favorite Companies: Nintendo, Blizzard, Valve.
Recent New Favorites: Grasshopper, Atlus. (R.I.P. Clover.)
Heroes/Homies: Shigeru Miyamoto, Gunpei Yokoi, Will Wright, Eric Chahi, Suda51, Brian Eno, David Bowie.
Haiku Group: Haiku Hell.
Nemeses: Snesboy, fkusumot.
GameDaily Article that Interviewed Me: Console Defense Forces.