Now that I've seen the whole anime, I have to write a whole new review because, well, it's that good. Plus I realized that the first episode actually takes place after the rest of the series, which is why it seems to be so different from everything else.
The story is about Gatts, a really buff guy who has a massive sword that Arnold couldn't lift but Gatts manages to use it one-handed sometimes. Gatts is haunted by the memory of his old mentor, and according to the manga the guy who actually adopted him, Gambino. Gambino was a soldier who raised Gatts to fight, but once he himself got too sick to fight any more he grew jealous of Gatts and tried to kill him. Gatts killed Gambino instead, but he regrets having to do so.
The main storyline begins when Gatts meets the Band of the Hawk, a group of mercenaries led by a young white-haired guy named Griffith. Griffith's one motivation is getting a kingdom of his own, and he'll do anything - and I do mean ANYTHING - to get it. Griffith sees Gatts' usefullness as a warrior, and challenges him to a duel. If Griffith wins, Gatts has to join the Band of the Hawk. If Gatts wins, Griffith will let him leave and not have his whole group gang up on him and kill him.
Naturally, Gatts loses, and a lot of the show deals with Gatts fighting as a hired sword in the Band of the Hawk.
But meanwhile we have Caska, the one chick in the band who still somehow manages to be the second-best fighter besides Griffith (and of course not counting Gatts). She wants Griffith to herself, but feels threatened by Gatts because Griffith chose him to be his great warrior, which is what Caska wanted to be, and plus because Griffith isn't too manly and might want Gatts in other ways as well. Fortunately Gatts doesn't swing that way, and just to make things interesting he develops a love for Caska.
If becoming the best mercenary army in the world and taking over a kingdom weren't hard enough, things are further complicated by a medallion Griffith owns called (usually) the Eye of the Gods. We're not entirely sure what it does for most of the series, but we know it's really powerful. At one point, Gatts and Griffith fight a demon (Zod the Immortal, quite a cool character actually), and Zod doesn't kill Griffith just because he sees the Egg of the Kings (that's another name for it, or another translation).
Anyway, I'd better stop there before I ruin too much more of the anime for you.
Be warned, though, this anime has got a fair share of sex in it (thankfully never overdone, and a lot of times things either aren't drawn in or are covered up), and more importantly it has a ton of blood, giblets, and violence.
Despite that, this is still an awesome anime. It's not even close to being wrapped up in the end, so I hope there'll be a second season soon.