Novels about a male cyborg space ship captain with a female feline humanoid business partner

I'm having a great deal of difficulty digging up details on these books, and I don't own them (I borrowed them from a cousin in 1985) but I suspect you may be thinking of Doom Star (1978) and Doom Star Number Two (1979) by Richard S. Meyers.

At the beginning of the first book the Black Hole has a crew of two: captain Larry Baker, a cyborg and his partner Napoleon, a humanoid feline woman. They pick up Harlan (Hal), a soldier/police officer with a space-going combat suit (space bullet) to pull off a rescue mission. (The woman they're rescuing might be the fourth member of the party you recall.)

In the second book they join up with a travelling Shakespeare company.

(Google books says: "Larry Baker, Napoleon, and Harlan join the Light Orbit Space Theatre, a space traveling Shakespearean troupe, and are soon in a battle with their old insect-like enemies, the Mantases")

The books were republished as Doomstar and Return to Doomstar (1985) under the name Richard Meyers.