Why do McGonagall and Umbridge share a patronus?

Well, they do have similar personalities, up to a point. Loyal, independent, disliking challenge, quick to anger, arrogant, that's what I came up with off the top of my head.
How well these shared traits are catlike, (or if there were traits in either that were catlike, but non overlapping) depends on how JK viewed cats.

Both of them seem loyal, but also exceedingly independent. McGonagall is very loyal to Dumbles, but also shows here independence by questioning or challenging him when she thinks it necessary. Umbridge seems to be loyal to Fudge, but shows her independence by exceeding her authority (committing crimes) without Fudge's knowledge so he would have plausible deniability. [Cats as companions, complete with strong opinions and offerings of mice.]

The fact Umbridge can switch her loyalty to Voldie after the Ministry falls, is also catlike - Fudge was gone at that point, and a cat's loyalty, unlike a dog's, can be rather immediate (loyal to those who are there, not so much those who are gone). McGonagall does not share this trait, but then I don't know if it's a requirement that she should - perhaps they are different cats like they are different people, or perhaps of the list of all things catlike, a person doesn't need all possible traits, and which ones they do have can differ.

Both prefer to have everyone follow the rules and believe in strict discipline. Any challenge to their own authority is treated very harshly, they are quick to anger. Obviously Umbridge is more severe and tends towards outright torture, but Mcgonagall has shown the trait as well. One example of harsh treatment in the face of challenge is the 150 points lost in PS, which she probably knew would get the trio shunned by their House, or letting Hagrid send them to hunt a unicorn killer (which seems really dangerous and excessive in retrospect). There are a couple other points, when catching someone who knows they're in trouble, where she seems to be toying with them. [Cats can be cruel, prefer to play with their prey, and don't like challenges to their dignity.] Possibly dislike of challenges to their authority comes from being territorial?

Of course, this deference to rules and dislike of challenges only holds to the authorities they respect - Umbridge is dismissive of Dumbledore, school rules, and the other teachers, McGonagall tends to be dismissive of individuals including Trelawney, Umbridge herself, and certain ministry policies. [Cats can be quite arrogant.]

Other differences between them might stem from the philosophies of the people they're loyal to, and the fact that McGonagall sees the students as hers (kittens to be taught and occasionally swatted) while Umbridge sees them as prey (to be toyed with and/or destroyed). So they're both cats, just different ones. They are both deceptive, in a way - McGonagall's tabby animagus form seems ordinary and lets her hide in plain sight, while Umbridge's fascination with kittens and the cute hides a vicious personality (...like some real fluffy kittens). [Cats are not straightforward... they're tricky.]

I don't know if this is the real answer, why they're both cats. Too much of that reason depends on how Rowling saw cats or intended the characters to be read. But it's what I thought of when I saw the question, so I thought I'd offer.