Probably not a defective fuel pump relay.

Check the fuses, and pay close attention to the fuse clips, the fuse caps (contacts at ends), and the tension of the clips. Retension (= bend) uf necessary.

I use a Scotch scrubbie pad (the green one) to clean the fuse clips. The green one is abrasive enough to scratch glass, so it clean the brass clips well, but it's non-conductive, so no sparks.

"...sounded like it was starting strong, but it would never actually turn over..."

This is unclear. Do you mean that it cranked strong but would not fire?

To say, "turn over" implies that it cranks. To say, "starting strong" implies that it fired strong.
--
Don Foster (near Cape Cod, MA)