In terms of the difference between the tow words for what we call in English, "work" here are some quotes from websites exploring this:
http://www.chabad.org/library/article_cdo/aid/95906/jewish/Melacha-A-Unique-Definition-of-Work.htm
"The Hebrew language has two words for "work"--avodah and melachah.
Avodah is a general term meaning work, while melachah has a very
precise halachic meaning. On Shabbat, melachah is prohibited. Our
Sages explain that melachah refers to the activities which were
necessary for construction of the Mishkan, the traveling sanctuary
which the Jews took with them throughout their desert wanderings."
http://www.torah.org/learning/ravfrand/5761/shemos.html
There is a difference in Lashon HaKodesh [the holy tongue] between the word Avodah and the word Melacha. Melacha (which we find, for instance by the forbidden Sabbath labors) connotes constructive work. Avodah is merely toil, without necessarily accomplishing anything.
https://www.shaalvim.org/sfw/shiurim/view.asp?id=598
The Ramban is saying exactly what the point of the Mishkan was. Everything Hashem instructed, Bnei Yisrael did as avodah. When Moshe saw how Bnei Yisrael were treating the seemingly unimportant, the tedious—the melacha—as though it was the avodah itself, he felt it fitting to give them a beracha (“Vayar Moshe es kol hamelacha, vehinei asu osa kaasher tziva Hashem ken asu vayevarech osam Moshes” 39:43) Rashi says this beracha was a yehi ratzon that the Shechina should rest in the work of their hands, “Yehi ratzon shetishre shechina bemaaseh yedeichem…” Moshe saw Bnei Yisrael’s loyalty, dedication, and complete sincerity for Hashem and wanted them to get their reward—a confirmation from Hashem that they indeed were worthy of His Shechina. In addition, it could be said—Bnei Yisrael spent all their time and so much hard physical labor for Hashem and all this melacha was indeed turned to Avodah.
a video shiur on the topic (17 minutes):
http://www.torahanytime.com/video/avoda-vs-melacha-regarding-shabbat/
and an audio one (33 minutes):
http://www.yutorah.org/lectures/lecture.cfm/743139/Rabbi_Aaron_Soloveichik/The_Difference_Between_Avoda_and_Melacha
The distinction between the two ranges from the legalistic dimension (as melacha is a particular category of behaviors) to the spiritual to the linguistic (with "avodah" also a word meaning "worship" (sort of) ).