I'm not a historian. Just an amateur. So while you're waiting for someone more qualified to pop in ( and you'll be waiting a while. Scholars of SEA seem quite rare here, and u/PangeranDipanagara , the user whose answers I've found most useful for the region on here seems to be largely dormant now.)

I'm just writing because I think your question could be answered better if you imposed more limits on it. SEA broadly extends today from Myanmar in the West to the Philippines. And the Middle Ages is from 500 to 1500 AD. That's a very long time and geographic area to discuss anything about in generalities. Even today, SEA has some of the world's largest cities such as Jakarta, Singapore and Bangkok while also being home to several tribal people, especially in the Kalimantan area of Indonesia.

Additionally, I would propose that the 'middle ages' is not the best term to group historical events outside of Europe. The medium aevum was an idea largely created, as I understand by my reading of answers from medievalists here, by Renaissance men, who wished to link their age of humanism to an earlier classical period of progress -- especially to the Greeks and Romans. The Middle Ages thus were made to seem like an era of darkness and social stagnation. This was barely true of Europe. When factoring in the Guptas in India, the Tang and Song Dynasty of China, the Heian period in Japan and the Islamic Golden age in Baghdad, talking of the Middle Ages in generalities becomes impossible. We'll need to talk about the history of different places within the context of their own historical groupings. Maybe u/sunagainstgold can give you some pointers on this. There was a link I rather liked on a discussion to debunk the Renaissance ideas of the Middle Ages. Let me see if I can find it for you.

And I'm afraid I can't give you a general overview of the whole of SEA. I know next to nothing of the history of Vietnam, Cambodia, Laos, Thailand and the Philippines. I know a little about Indonesia, by virtue of living there. And even so, not from academic sources. But it's a place for you to start.

At least in Indonesia, the major political entity was the Srivijaya Empire, based in Sumatra, extending into the Malay peninsula and West Java. The Srivijaya were Buddhist and were a force for spreading Buddhism in SEA. The other major political entity was the Javanese kingdom, who were largely Hindu.

There were definitely tribal populations, but there were also large urban centers, such a Palembang and Yogyakarta. The Borobudur, even today the largest Buddhist temple in the world, was completed in the 9th century by the Srivijaya empire. Brisk trade in cloth, spices and animal produce with China and India boosted the economy.

In the 13th century, the Srivijaya Empire declined, giving way to the Singhasari in Sumatra and the Majapahit Empire in Java. By the 15th century, Islam was being introduced to the region by traders from India and the Middle East.

I won't continue speaking on this topic as I just don't know enough. But if you're interested, I highly recommend reading up on your own about it. If you're at a University, you should be able to find some good sources.

As for the Melanesians, I believe they were a people occupying an archipelago even further east than Australia and wouldn't generally be classified in the SEA region. The Dayaks of Borneo, for example, are an aboriginal people in SEA.

As for dengue fever, I'd love to hear more from an expert on that too.

Was dengue fever incurable then and everyone who got it just... died?

This isn't historical but dengue fever and dengue hemorrhagic fever are caused by virus and has no anti-virus for it even now, only vaccines. If you caught it you'll get better as time passed by the virtue of your own immunity. Dengue fever isn't life threatening but it can develop to dengue hemorrhagic fever which is life threatening. You may need blood transfusion for severe cases of DHF. You may take some medications to ease the symptoms like fever or body pain, but there is no cure for the disease itself like TB cure. You'll get lifelong immunity if you're infected, though there are 4 different viruses so you may caught more than one. And if you have good immunity, you can get infected with the virus but have no fever or any other symptoms.

Here I can cast in some common knowledge on Vietnamese history.
As /u/Anon4comment has stated, the term "Middle Ages" is not really poignant to describe SEA history. For example of Vietnam, the time line would be better divided as Chinese colonization period (3rd century BCE - 9th century CE), middle age (9th century CE - 19th century CE) and French colonization (1858-1945).
For most of the time between 500-1500 CE, modern day territory of Vietnam consist of mostly 3 entity:

1. the Chinese Jiao province (also known as Giao Chau, Linh Nam, An Nam colonization office... depend on period) covers modern day North Vietnam. After 9th century, the region gain independent as Dai Viet kingdom, an autonomous tributary state of China. Dai Viet's power base is in the densely populated Red River delta with a large body of Kinh ethnic; mountainous area to the North and West are home many minor ethic tribes who prove to be either valuable allies or threats of rebellion. Dai Viet's culture took heavy influence from China in term of philosophy, bureaucratic organization, architecture... Confucianism are the state's official ideology, bureaucrat exam was held similar to that of China. Buddhism also poses a large influence with both common people and the ruling elite pre 15th century. About military, I don't know much about earlier periods but by 13th century, Tran dynasty successfully repels Yuan mongol invasions, relying on personal armies raised and kept by various lords of the royal clans, supplemented by peasant levies, trained war elephants act as shock troops. In late 14th century, firearms are also incorporated and is widely used by 15th century.

2. Champa Kingdom covers the seaside area of Middle & South Vietnam. Opposite to Daiviet, Champa took after Indian influence with a mixture of Hindi, Islam and Buddhism heritage. Their demography consists of various ethnic: Cham, Kinh, Hoa (Chinese origin)... Unfortunately Champa history is rather understudied and suffered from a lack of primary accounts. Although Dai Viet sources are often patronizing toward Champa, there is little doubt that they are a complex society and a significant military power in the region, managed to repel multiple invasions from the Angkor empire, Dai Viet and Yuan mongol during 900 years of its existence.

3. Most of South Vietnam are territory of Angkor empire. Dai Viet often expand its border southward at the expense of the Champa and the Angkor, and by 17th century, this region is firmly under control of Vietnamese house Nguyen.