12 Kingdoms is definitely required watching. There's not many heroines where the story takes the 'beat the shit out of 'em until they're tough' approach.
Berserk is actually fantastic, but I understand people who get initially turned off by it. I had a hard time making it through the initial episode or two, I was reassured that it was great, so I tried reading the manga... similar deal. But trust me, once you make it through the rocky beginning, it's waaaay worth it.