I have all of the little connections going to the same side of the Solenoid. Is that right?

Oh I thought this meant you had more then one small wire, two like the newer trucks have.
The relays seam to all come with 4 posts now, probably because they work with both applications, but should have included a small jumper for use on the 3 post apps.

So yea, jump a scrap wire from the positive battery post to the small unused post on the relay then try the key, if it cranks over make your own little jumper and you'll be all set.

Make a short jumper to go from the large "battery" post on the relay to that little post.