I agree, that leveling up could take too long and bore characters. One thing I did like in Fallout was that character levels didn't change the game that much. You only got a few health points and a few skill points but getting the perks were rare and most of the early perks weren't that helpful (although a few like awareness were very important).
But more traps would be interesting. More big bad critters would be great. A giant cockroach is only so effective, but I loved the talking rats in FO2.
At the same time, the aliens in the hold of the tanker just seemed like laziness. "Oh we need to make this tanker story more interesting so lets create a monster in the ship and use aliens. It worked for Redding." Come on. If they wanted a monster in the ship, it could have been more interesting. Imagine, for instance, having the character explore a dark hold where they really can't see much and encounter something nasty, like a mutant octopus that's using the ship as a source of food, or some other predator that we haven't seen before. Perhpas it's killing the crew one by one and they keep disappearing. That might not be the best idea, but it's better than aliens walking around in the hold of a ship.
Mutant vultures would be fun. But even something that makes the character have to think. For instance, there could be an encounter where the entire town is suffering from a disease, and the character has to use his science and health skills to figure out what the disease is. The virus itself could be the monster in that case.
I agree with you, the training in Age of Empires 2 was really good, and it's one of my favorite games, mostly because I thought they gave a pretty good product (although the conquerors' expansion improved it).