Not sure if this is your issue, but after replacing a starter years ago with one that did not have the extra wire dangling from it, my truck would sort of act like yours. Turn key, CLICK. Try again and it would turn over, but sometimes taking more cranking time to start then usual. After warmed up it would start right up fine. This went on for quite a few years until a mechanic mentioned that my truck was not getting a full 12v during the startup. After which, once it's running will lower to about 10 or so volts. I did some research on starters for our trucks and I noticed an extra wire that connects to the starter solenoid on the side that the cable comes out of the starter and other end of wire goes to the coil. Think it's shown as an inhibitor wire and usually used on automatic trucks to make sure shifter is in Park. I didn't remember ever seeing one on my truck before, but during a rebuild I unwrapped some taped up harness wire and found this extra wire and connector wrapped in and it was close to this area of the engine. I connected this hidden taped up wire to the starter solenoid and the truck started immediately on the first hit of the key. No more clicking on startups and repeated tries to get it started. It starts instantly now.
This may or may not pertain to your issue, but usually if your just getting a click on starting and battery is good and stuff. Make sure your getting full 12volts to starter when you turn key to start it up.