Designing Monsters Is Fun,
Lovecraft's monsters don't actually translate that well to Quake, because his stories aren't about badass soldiers killing things with rockets. Quake may have channelled some of the essence of Lovecraft in its visuals and naming conventions, but that's really where the similarity ends so I think it's a mistake to look for specific mythos creatures to turn in to bosses. Instead do what ID did, and design something new that fits an action game.
I took the liberty of sketching out a couple of concepts this morning:
Apologies for poor image quality, I'm not near my scanner.
URTHKLAH can move through walls like a ghost and when she's really angry she'll charge with all of her front mouths. Her back mouth fires a volley of zombie gibs. Think projectile vomit. If a gib volley completely misses the player a zombie gets spawned wherever they hit.
MECHOGRE has a slow turning circle so it's wise to get behind him to avoid his charge and rocket attacks, but as soon as you do so he'll launch a volley of grenades to keep you busy dodging whilst he turns. And yes, he does have a giant toothy vagina. It's purely for decoration though, so don't get any ideas.