I rarely start with music but sometimes I do. Normally, after the first few lines, I'll know the structure. I may compose the tune next or complete the lyric to a dummy melody that will be replaced by something later. The lyric is not finalized until the tune is composed. My very last step is arranging and adding chords — I'll often do a Lead Sheet first as that can point to weakness n the structure.
So, for me, the correct answer really is, "It all depends."
The late, great Burt Bacharach, when asked the same question, replied, "No one ever left a theater humming the lyrics."