You should watch
Zetsuen no Tempest (it's still airing). It’s a fantasy action that involve magic just like
Fate/Zero. It's also pretty much unpredictable in which the mysteries are layered and they also reveal the overall plot slowly within each episode. Very enjoyable stuff. Oh, and this is
not a yaoi show even though the protagonist are two bishies, just in case you don’t like yaoi or stuff like that
.
Oh, and I also recommend you
Basilisk. An action show set in feudal Japan that involves two groups of ninjas (ten people each) from different clans battling each other for pride. Again, kinda like
Fate/Zero, but here, they use ninjutsu instead.
There's also
Saint Seiya: The Lost Canvas and
Fuuma no Kojiro which are also great.