French: I'll second City of Lost Children, La Femme Nikita, and Brotherhood of the Wolf. Here in Boston, the Museum of Fine Arts hosts an annual French film festival (sorry, I forget when).
German: Das Boot, already mentioned, and Stalingrad are great for us WWII/history nerds. Someone already mentioned Run, Lola, Run; Franka Potente was also in Anatomie and The Princess and the Warrior, the latter of which was directed by Tom Tyker (who did Lola). Tykwer also did a movie in...
Italian: Heaven, starring Giovanni Ribisi and Cate Blanchett. Cate Blanchett rules in any language.
Norwegian: The original Insomnia was pretty good.
Korean: I just saw Shiri recently. I wasn't blown away, but it had it's moments, and I'm sure it could generate some ideas for Spycraft. There's a cool-looking Korean sci-fi movie that I want to see. I think the trailer was on the Shiri dvd. If anyone can find the name of it, I'd be grateful (it seems silly to rent the dvd again, just to see one of the trailers).
Japanese: Kurosawa was already mentioned, so just add my name to that list. You can find Ringu in most video stores, and The Eye is coming soon, I think.
Spanish: Pedro Almodovar's movies have been on screens here for years. I recently saw Hable con Ella.
Chinese/Hong Kong: There's usually one HK film festival around here every year. Jackie Chan and John Woo have already been mentioned. Also look for The Heroic Trio and anything by Wong Kar Wai (Fallen Angels and In the Mood For Love are my favorites).
Chinese: You mentioned Hero; Zhang Yimou's earlier movies, with Gong Li, have been available in this country for years.