Melody should always come first IMHO
If I can't hear the melody, then it's just some guitar player improvising and calling it a song.
One thing that bugs me is the guitar players who say their playing "jazz standards" and you never hear the melody until several minutes into their playing.
Somewhere Over the Rainbow shouldn't start with a 3 minute improv.