Don't go down the wrong path. Your fuel stop solenoid will not cause what you described. They are not garbage either, only for people who run batteries more than 5 years old in their trucks, yet keep them because they still start the truck (but voltage then drops below solenoid spec during cranking). They do have 2 coils in them, a pull and hold, hence the 3 wires.
Yes you are sucking air. Replace the soft lines from tank to lift pump. Pull and check or replace the tank dip tube as mentioned. Test lift pump while cranking truck with spin-on filter loosened. If you have the large frame mounted canister filter, make sure the square washer at the top is seated correctly, and the drain at bottom is closed correctly. Your main injection pump should be fine if your filter was only half full. The push primer only works well if you crack the spinner filter loose or loosen a bleed screw at the lift line top banjo fitting or injection pump bleed screw (both 10mm heads).