A Gilliam Watchmen mini-series would've been amazing, imo. He's kind of a mad genius. Very hit-and-miss, but that's one of the things I like about him - he never plays it safe, which is why studios are scared of him and actors want to work with him. Brazil and 12 Monkeys are 2 of my favorite movies of all-time. Gilliam also co-directed Monty Python and the Holy Grail with Terry Jones, fyi, and of course, as Gilpesh pointed out, he did all of the animations, as well.
He wouldn't be as slavishly faithful to the source material as Zack, though. The guy's imagination works overtime, which is why he would need it to be a miniseries - to flesh out the universe with his own little crazy ideas. But one thing's for sure - with Gilliam, there would be Squid. He would relish the opportunity to create that thing on screen, and nothing is too weird or "out there" for him. He also has a seriously obsessive attention to detail which would've served the series well.
And for the record, I'm sure it wouldn't have looked like his Monty Python work. Its "look" would probably have been more similar to (while not exactly like) 12 Monkeys (ignore the random music):
[YT]fsihX3vh5Jw[/YT]