Much of the remedies for your situation depend on what you have in writing about 1) the transmission agreement and warranty you signed and what it may contain about warranty replacements, arbitration and court actions, and 2) what written evidence you have to the fact that the garage was encouraged to "keep trying things" until the warranty ran out, as well as evidence of the dates of the CEL (check engine light) maintenances and the shift solenoid replacements.
Do you have - or can you get - a statement in writing from the garage that they were told to keep trying things until the warranty ran out? Your case to get the company to pay for the installation of the new transmission may hinge on this, as you need to prove that the transmission was possibly failing before the end of the three years.
Does the transmission sale and installation agreement contain a clause about binding arbitration or court actions if you have a warranty complaint? These will determine what you can and can't do if you exhaust all other remedies and want to go to court.
But it sounds like the transmission company is at least trying to make the situation whole by offering a replacement transmission. You need to gently push them to pay for the installation.
Your basic options are: 1) you can try to talk to the transmission company yourself (along with the ammunition of possible evidence of the garage being told to delay warranty replacement) and try to work out a settlement for them to pay the installation costs; failing that, 2) file a complaint with a consumer advocate (like Consumer Protection | Washington State); or failing those, 3) take the transmission company to small claims court (if your agreement does not bind you to arbitration).
Re: the first option above: something that can work very well is if the transmission company is a regional or national chain, look up the president or CEO and send them an email outlining your complaint. Many times a corporation will try to settle these types of situations before a complaint is filed or they go to arbitration or small claims court, because good PR (paying for the labor/installation) is cheap and bad PR is expensive. They already offered a replacement transmission, which is good; you need to gently push them to pay for the installation.