Naruto's second OP made me a big fan of Asian Kung-Fu Generation. Haruka Kanata is the one and only Japanese songs that I know the words to, by heart, from start to finish. Granted it's not the most complicated of songs, but it still impresses my nerdy friends.
Their full length record Kunkei Five M is really fantastic stuff.
Oh and the Pillows rox city blox too. Those guys are incredible musicians. The FLCL OST's are amazing.