Keep writing - like steve says - and keep listening. The more melodies you hear, the more they all go into your brain and cross-fertilize with one another. You start to get an instinct for good melodic tricks, for the shapes of phrases.
There are rules you can discern from analyzing melodies (given enough melodies and enough time), but composing your own has to be intuitive in the end.
Your instinct is right that it's melody that matters. When that comes first, you tend to get a good song. (You can't sing a chord sequence, after all...)
What I find helps is to have some words too: just a few, to go with a hook phrase, maybe no more than 4 or 5 notes. The words don't have to lead anywhere, or even make much sense, but they're a hook to hang the notes on, to help make them
singable, so you can hold the tune in your head and let it lead you on.
Remember Paul McCartney's "Yesterday" started off as "Scrambled eggs / oh baby how I love your legs" - IOW, just some nonsense to hang the tune on, to help remember it and work on it.
Of course, if you start off with some great words in the beginning, even better. Words come with their own rhythms, and even suggest melodic shape a lot of the time. The point is always to keep a tune singable - even if it's destined to be an instrumental piece, you want people to go away humming it.
Another tip is to actually steal a melodic phrase you like from a favourite song - then take it somewhere else. Obviously make sure it's either a short one, and/or one you can edit in some way to make it less recognisable. I often hear phrases in songs that I think could be remade to lead somewhere else, and become a new song. You quite often hear phrases in popular songs that remind you of older songs - that may be accidental (subconscious theft or simple coincidence), or it may be deliberate;
hommage, stopping short (hopefully) of actual plagiarism.
The more influences you combine in your music, the more "original" it will sound. What made the Beatles and Dylan (to name just two) so great - and so "original" - was the breadth of their influences: they simply listened to far more stuff than their contemporaries. And not only that, they absorbed it all and regarded it all as fair game, as suitable raw material. It was never a question of limiting their listening to whatever was supposed to be "cool".
Like Duke Ellington (supposedly) said: "There's only two kinds of music: good and bad. I like both kinds."
;-)