Melody vs. Harmony. Where to begin?

[BandArrangers.com]

Sometimes I will come up with an idea where I am just messing around with the piano.

A little idea can go a long way. And one idea can lead to another. For me, sometimes it is a chord and sometimes it is a hint of a melody.

[ralphb]

Melody, always. You can have a good theme with unspectacular harmonization with great success (see Classical era compositions), but strong harmony with a lousy theme is much more problematic.

Another thing is, that you need both things, and the best way (most listeners are used to) is to write a memorable theme and then play with it. While playing (developing), you can focus on harmony and adapt the theme!

[Student]

Neither, start with form and/or structure.* If you don't know what you're going you'll end up with a piece that wanders aimlessly almost every time.

I recommend sketching out a quick outline of the piece in a notebook. There's no reason to follow it stringently but having an idea where you're going is immensely helpful.

*Well you could have either a harmonic idea or a melody that you build the piece around as well as a structural idea, but then you still have a structure in mind (theme and variations, ground bass, continuous variations etc.)