They don't really deserve it but then no one else does either.
This.
There should not be a nationwide primary, there should just be a few states doing it at a time. Since no state deserves to be first all the time, the order in which states hold contests should be randomly selected through a lottery each cycle. One state can be randomly selected for the first primary, then two for the second time, and three for the third round. After that, the number should not exceed five.
A nationwide presidential primary would be problematic in a field of multiple candidates, and holding a few contests at a time can help eliminate candidates aren't fit for the long haul. But no state should be entitled the special position of first all the time (and I say this as someone originally from Iowa).