Kings, which retold the biblical story of King David in a modern setting; it was very short-lived and had some issues, but Ian McShane was tremendous and I think the premise had a lot of potential.

The Riches, another show that only got a couple of seasons. It was about a family of Irish Travellers and starred Eddie Izzard and Minnie Driver.

Babylon 5, a really unique sci-fi show that, while it had a dedicated fan base (and still does), never got the credit it deserved for helping to usher in a new generation of genre shows with a polished, pre-conceived narrative arc that stretched over several seasons.

Rome, a show that definitely isn't underrated, but I think fits the bill of being underappreciated by the general public. The writing, casting, set/costume design, cinematography and music are all top-notch, but the acting is really something else: Kevin McKidd, Ray Stevenson, Indira Varma, Ciaran Hinds, Kerry Condon, Tobias Menzies, James Purefoy and Polly Walker all give tremendous performances. Without it, Game of Thrones would have never existed.

I'll agree with you on Deadwood as well. I think the dialogue and the slow-burn pacing makes it a bit of an acquired taste, so I can see why it's not as massively appreciated as it should be, but it's Milch's magnum opus. The writing is just so good, and Ian McShane is simply next-level.

As a slightly silly honorable mention I'll also add The Adventures of Brisco County Jr. A whacky steampunk western show starring Bruce Campbell that was unlike anything I'd ever seen before. It wasn't the best show of all time or anything but I never see anyone talk about it at all. Kind of a shame, it was a lot of fun.