Starter came to mind for me as well, of course.
If you're going to push start it, reverse is easier than 1st anyway, since it's shorter.
Main relay being bad will cause no start but since you have dash lights, etc. I don't think so.
I doubt there is enough corrosion on the battery terminal on only the cable that leads to the starter but you never know. Check to make sure the cable didn't lose connection to the starter somehow, that's the first place I'd check.