Stop in for a cup of coffee

OK. I'm going to guess that there is enough power (Watts) to the starter when the solenoid is directly connected to the battery. And not enough juice getting through when going the relay.
So the question is why?
Some possibilities:
Weak battery?
Restriction in the circuit to the solenoid?
Starter failing and demanding more power?
It sounded like it was spinning good the first few revs then clicked. I would point to the starter but I have a battery tester to eliminate that if it's a issue. There may be a bad/loose connection there somewhere. Where is the battery grounded to and do you have ground straps from the block to a good spot on the firewall? Please answer one question at a time.