Do you know if the fuel filter has been changed? Lots of places quietly skip it as it's a pain to do. But in my experience an old, clogged fuel filter is often the reason for poor starting which wrongly gets put down to battery, plugs etc.
First of all, check (clean and grease) all connectors between battery, relay and starter motor; also clean connector on earth wire bolted to engine and earth wire fitted to ECU. Next step good battery, gel would be better than acid.