I saw "Hero" last night with Katie & Keith. It gets an emphatic two thumbs up. It's told in a surreal fashion, with dramatic use of color as the main part of the story gets told three times from three different perspectives. The martial arts are at the fantasy level -- Jet Li does a handspring off the surface of a lake at one point -- but appropriate to the characters, who are all larger than life. Despite a large cast (there many action sequences where huge armies cross the land), there are really only four main characters in the movie, and it ends up being about the interaction between these four.
The movie ends with a strong dose of Chinese nationalism, which undoubtedly gave it the enthusiastic support of the Chinese government. However, it doesn't seem out of place, as this also ties together the story of the four characters.
Note: not a good pick for those allergic to subtitles.