The way I see it, there are two extremes in sword-clashing medieval fantasy anime. You've got your serious epics of heroes trying to save a war-torn society from complete darkness (Berserk, Bastard!, Record of Lodoss Wars) and your bumbling fools that walk into a feudal situation, only to comically flee the town crisped from dragon's fire (Slayers, Sorceror Hunters, Those Who Hunt Elves). There have been lots of shows that have tried to fit themselves between the two poles, but the real successes appear to be those that decide on one or the other.
By its title alone, The Legend of the Legendary Heroes (Densetsu no Yûsha no Densetsu) appeared to be redundant and pushing for that comical side; aren't legends supposed to be legendary in the first place?
The story was originally composed as a light novel by Takaya Kagami, who shared the "Dragon Cup" in 2001 for the best short novella, according to Monthly Dragon Magazine. The anime has been directed by Itsuro Kawasaki (Arc the Lad, L/R, Chrome Shelled Regios) and produced through Studio Zexcs (Sister Princess, Da Capo, Chu-Bra!), so the series is getting a surprising mix of both expertise and newness to the fantasy genre.
The story is a little difficult to process from the first episode, as we are introduced to two citizens of the Roland Empire who have been granted the task of assembling the relics from the legendary "Legends" from the past that have defeated the demonic lords of the land. The male protagonist, Ryner Lute, despite his laziness, possesses an ability called "Alpha Stigma" and is able to copy any magic thrown at him. His partner, Ferris Eris, is a talented female knight with an affinity towards dango dumplings.
While the first mission ends up like many of the "successful failures" on the comedic end of the fantasy spectrum, it is the underlying story that pushes it closer to a serious drama. It is those Alpha Stigma eyes that have gotten Ryner a disposition as a monster after he mowed down a rebellion from Estabul. Ferris's own past appears to be connected with the nature of her House and uneasy relationship with her siblings. Overseeing the mission is the third dramatic piece of the puzzle in the newly-minted king Sion, who has overcome his past as the son of a royal and a commoner to take the throne.
While Ferris and Ryner appear to have fallen into the flipflopped roles once occupied by Lina and Gourry from Slayers, the story has some rough terrain to traverse. The past is retold quite dramatically, some of the images quite drastic in gory portrayal, while the present mission can't decide whether it wants to be lighthearted or grim. This is likely the reason the series will be going a full two seasons—the show is a bit confusing to digest in the first three episodes and requires a lot more time to weave the story between the three households in Roland.
That being said, while the art is quite graphic and told at a fast rate in the action sequences, it's hard to really place Legend of the Legendary Heroes in one of the two extremes. That might cause the story to fail to attract viewers, as there really is nothing exceptionally unique about the show. Relic-hunting has been done before, and the settings are nothing new to the experienced eye. It's also hard to envision the direction the show may go, although it is likely that the story will revolve around Ryner's desire to not get involved in politics on the battlefront.
Frankly, I'm unsure just how long the average viewer will be attached to Legend of the Legendary Heroes. The fantasy genre doesn't seem to be doing so well in anime, save for those that decide to focus much more on acting and character personality than character design and the actual battles themselves. The show may merit a few more episodes, but it's going to require much more than just a war to capture the attention of starving fans.