Since the battery is new, you can eliminate it. That leaves the wiring, connections, and starter. After visually checking the wiring and connections for corrosion, loosness, etc, you will need to do a voltage drop test on the starting system wiring. Over all starting system should have less than .6 voltage drop with .1 or less for each connection. With the ignition system disconnected, you will need to crank the engine about 5 seconds for each connection you are testing to let the reading line out. If your system passes the voltage drop tests, you starter is the problem. It just don't have enough balls to start the motor hot - especially when it is also hot. You can do some things to help it - as mentioned, but the problem is still the starter.