I have two Winchesters as follows:  1876 40-60 and 1886 38-56.  Both need to be rebored to larger calibers.

Looking for new caliber recommendations.

Looking for recommendations of who to rebore them.

Thanks.

Some of what you can re-bore and re-chamber to will depend on the condition of the current chamber. If the chamber is in good shape in both rifles you do have a few options. They are currently using cases based on the 45-70 case head so that gives you a few options. In the '76 you can move up to the 44-60 or the 45-60. They are the same case length just a bit fatter bullet. Unless the pits in the barrel are overly deep either should be doable. 44-60 cases are easy to make, and you would be looking at a 385 grain gg bullet over about 55 or so grains of bp. the 45-60 is just trimed back with a very slight bottleneck. 
As to the '86, others will correct me if I am wrong but I think the current cambering is also based on the 45-70 case, that being the case next step up would be a 40-65, then 45-70 and then up to the 45-90. Next steps up would be to a .348 or to the .50. Those would require the bolt face to be opened and maybe some other modifications to the insides . So you do have a few options to work with.
Sam

Can't go 45-70 in an 1876 Winchester. Too long. 45-60 longest you can get through it. moodyholler

Would it be better to recline the barrels to the same caliber?  I know it would be slightly more expensive but the barrel markings would be correct.  I just had JES rebore a barrel to 50-70 and it appears that it will be a shooter!  Super fast turnaround and $350  including rechambering and cutting two dovetails and return postage.  Tom

Go with the .50-95. It is a blast to shoot, and a good deer killer too.
Lee Gibbs pres.ASSRA 

P.S. in the 1876