The Gloomy Man wants you to deliver a Letter to someone at the Pub in Balterossa. After you accept the quest you will gain access to The Southwestern Road which will take you to Balterossa. Alternativerly you can do the quest "The Trade Route" to gain access to Balterossa. Find the "Cheerful Man" in the Pub at Balterossa to deliver the letter and receive your reward.
Spoiler warning: This section may contain information that could spoil the story line or displays in depth quest or fight details.
Gloomy Man: "Hey... This letter... It's gotta get to the Balterossa pub... Could you, maybe..."
Rush: "Quit harshing my buzz."
Gloomy Man: "Ahh... Figures..."
Rush: "...Take it for you? Sure."
Gloomy Man:"To get to Balterossa... Take the Southwestern Road... The guy there will reward you probably... You don't have to tell me about it later—it's not like anyone cares about me, anyway... Thanks..."
Cheerful Man: "Hey hey hey! Great! I've been waiting for this letter! Waiiit a minute... You didn't peek inside and read it, now, did you?"
Rush: "Of course not!"
Cheerful Man: "Right, right! I knew no true mail deliverer would commit such a breach of trust!"
Rush: "Ahahah... maybe a little?"
Cheerful Man: "Boring, wasn't it? This guy's letters are always so dull. Anyway, here's for your trouble. You had to come all the way out here, right? Thanks! Have a good one!"