Cranks slow with the key, fast at the relay

Forgive me....I didn't mention that I swapped in another starter relay and the symptoms persisted.
What is strange is that it isn't consistent. This does lead me to believe that the issue could come down to a loose or poor connection somewhere.