There’s not too much to choose between standard leisure batteries. I guess you are looking at 100 to 120 amp/hour.
Usual sources might be Boulters, Panks in Norwich, Battery Specialists also In Norwich, even Halfords.
I always use Paul at Rotating Electrics in Yarmouth (01493 330404) as he has a wealth of knowledge and in a fellow boater!
No need to change the starter battery unless it too is knackered.
I reckon the cost is around £100 per unit.
Hope that helps, but I’m sure others will be along with more help.