I vaguely remember a cartoon about a whole planet's survivors searching for a new home world. They all traveled and lived in a huge ship. Every episode they found a suitable planet and were chased off. At the end they all got back on board to find a new home. It was so sad I cried at the end of every episode. It is driving me crazy to remember the name of the show.
Best ones I can think of are Ulysses 31 or Star Blazers, both of which may work. Ulysses 31 is a rebelling of The Odyssey in space, while Star Blazers was a retranslation of Battleship Yamamoto.
Frankly, neither of these quiiiite fits, but I figured it was worth assuming some memory drift. Your mention of the serious tone of the show makes me lean more towards Star Blazers. From Wikipedia: "Many fans regard Star Blazers as more "adult" than other cartoons shown in the United States at the time, as personal tragedy, funeral scenes for fallen comrades, and the extinction faced by humanity were left intact. The very Japanese theme of "the honorable enemy" was also a tremendously important aspect of character development; in particular, the major villain of the first series, Desslok, during the second and third seasons, as well as in the later movies."
The show sounds like Battlestar Galactica more than anything, and I would urge you to look up the original show (given the time period) and see how familiar it seems. It was indeed about the last of humanity on a starship always searching for a new home, and every episode they thought they found a new one only to end the episode by continuing on their travels. I mean, had you not said animated, that would have absolutely been the answer, to such a degree that I genuinely urge you to take a look and see if maybe you were mixing up memories.